# Algorithm Improvement through Performance Measurement: Part 4

### Signed

Signed integers use 2's complement format shown below, with the binary representation on the left and its decimal value on the right:

Note that the most-significant-bit (MSB) serves as the sign bit. However, its meaning is opposite of what is needed for sorting [3]. The implementations in Listings 1, 2, and 3 work only for unsigned numbers. Radix sorting methods for unsigned numbers in [1] and [3] were extended to handle sorting of signed numbers by processing the most-significant-bit in [1] and the most-significant-digit in [3] as a special case. The same method is used in the signed sorting algorithm implementation in Listing 4.

```
// Copyright(c), Victor J. Duvanenko, 2009

// A set of logical right shift functions to work-around the C++ issue of performing an arithmetic right shift
// for >>= operation on signed types.
inline char logicalRightShift( char a, unsigned long shiftAmount )
{
return (char)(((unsigned char)a ) >> shiftAmount );
}
inline unsigned char logicalRightShift_ru( char a, unsigned long shiftAmount )
{
return (((unsigned char)a ) >> shiftAmount );
}
inline short logicalRightShift( short a, unsigned long shiftAmount )
{
return (short)(((unsigned short)a ) >> shiftAmount );
}
inline unsigned short logicalRightShift_ru( short a, unsigned long shiftAmount )
{
return (((unsigned short)a ) >> shiftAmount );
}
inline long logicalRightShift( long a, unsigned long shiftAmount )
{
return (long)(((unsigned long)a ) >> shiftAmount );
}
inline unsigned long logicalRightShift_ru( long a, unsigned long shiftAmount )
{
return (((unsigned long)a ) >> shiftAmount );
}
inline __int64 logicalRightShift( __int64 a, unsigned long shiftAmount )
{
return (__int64)(((unsigned __int64)a ) >> shiftAmount );
}
inline unsigned __int64 logicalRightShift_ru( __int64 a, unsigned long shiftAmount )
{
return (((unsigned __int64)a ) >> shiftAmount );
}
template< unsigned long PowerOfTwoRadix, class _Type >
inline unsigned long extractDigitNegate( _Type a, _Type bitMask, unsigned long shiftRightAmount )
{
unsigned long digit = (unsigned long)logicalRightShift_ru((_Type)( a & bitMask ),
shiftRightAmount );    // extract the digit we are sorting based on
digit ^= ( PowerOfTwoRadix >> 1 );
return digit;
}
template< unsigned long PowerOfTwoRadix, unsigned long Log2ofPowerOfTwoRadix, long Threshold, class _Type >
inline void _RadixSort_StableSigned_PowerOf2Radix( _Type* a, _Type* b, long last, _Type bitMask, unsigned long shiftRightAmount, bool inputArrayIsDestination )
{
const unsigned long numberOfBins = PowerOfTwoRadix;
unsigned long count[ numberOfBins ];

for( unsigned long i = 0; i < numberOfBins; i++ )
count[ i ] = 0;
for ( long _current = 0; _current <= last; _current++ )
// Scan the array and count the number of times each value appears
count[ extractDigitNegate< PowerOfTwoRadix >( a[ _current ],

long startOfBin[ numberOfBins ], endOfBin[ numberOfBins ];
startOfBin[ 0 ] = endOfBin[ 0 ] = 0;
for( unsigned long i = 1; i < numberOfBins; i++ )
startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ];
for ( long _current = 0; _current <= last; _current++ )
shiftRightAmount ) ]++ ] = a[ _current ];

if ( bitMask != 0 )    // end recursion when all the bits have been processes
{
if ( shiftRightAmount >= Log2ofPowerOfTwoRadix )
else												shiftRightAmount  = 0;
inputArrayIsDestination = !inputArrayIsDestination;
for( unsigned long i = 0; i < numberOfBins; i++ )
{
long numOfElements = endOfBin[ i ] - startOfBin[ i ];
if ( numOfElements >= Threshold )
else {
insertionSortSimilarToSTLnoSelfAssignment( &b[ startOfBin[ i ]], numOfElements );
if ( inputArrayIsDestination )
for ( long j = startOfBin[ i ]; j < endOfBin[ i ]; j++ )	// copy from external array back into the input array
a[ j ] = b[ j ];
}
}
}
else {	// Done with recursion copy all of the bins
if ( !inputArrayIsDestination )
for ( long _current = 0; _current <= last; _current++ )
// copy from external array back into the input array
a[ _current ] = b[ _current ];
}
}
template< class _Type >
{
const unsigned long Threshold             = 100;
const unsigned long PowerOfTwoRadix       = 256;
const unsigned long Log2ofPowerOfTwoRadix =   8;

unsigned long shiftRightAmount = sizeof( _Type ) * 8 - Log2ofPowerOfTwoRadix;
_Type bitMask = (_Type)( ((_Type)( PowerOfTwoRadix - 1 )) << shiftRightAmount );	// bitMask controls/selects how many and which bits we process at a time

else						insertionSortSimilarToSTLnoSelfAssignment( a, a_size );
}

```
Listing 4

This implementation works for various sizes of signed numbers, such as char, short, int, long, and int64 data types. The main idea is to invert the MSB of signed numbers and then sort based on the resulting bit or digit, but only for the most-significant bit or digit, and treat the rest of the bits or digits as unsigned.

In Listing 4 the top-level template function RadixSortMSDStablePowerOf2Radix_signed<>() calls the template function _RadixSortMSDStablePowerOf2Radix_signed<>() which uses extractDigitNegate<>() template function to extract the MSD and then invert its upper bit. For the next level of recursion _RadixSort_StableUnsigned_PowerOf2Radix_2<>() template function is called (in Listing 3), which processes the next digit (as well as the rest of the digits) as unsigned by calling itself recursively.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>