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 ],
bitMask, shiftRightAmount ) ]++;
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++ )
b[ endOfBin[ extractDigitNegate< PowerOfTwoRadix >( a[ _current ], bitMask,
shiftRightAmount ) ]++ ] = a[ _current ];
bitMask = logicalRightShift( bitMask, Log2ofPowerOfTwoRadix );
if ( bitMask != 0 ) // end recursion when all the bits have been processes
{
if ( shiftRightAmount >= Log2ofPowerOfTwoRadix )
shiftRightAmount -= Log2ofPowerOfTwoRadix;
else shiftRightAmount = 0;
inputArrayIsDestination = !inputArrayIsDestination;
for( unsigned long i = 0; i < numberOfBins; i++ )
{
long numOfElements = endOfBin[ i ] - startOfBin[ i ];
if ( numOfElements >= Threshold )
_RadixSort_StableUnsigned_PowerOf2Radix_2< PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( &b[ startOfBin[ i ]], &a[ startOfBin[ i ]], numOfElements - 1, bitMask, shiftRightAmount, inputArrayIsDestination );
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 >
inline void RadixSortMSDStablePowerOf2Radix_signed( _Type* a, _Type* b, unsigned long a_size )
{
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
if ( a_size >= Threshold ) _RadixSort_StableSigned_PowerOf2Radix< PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( a, b, a_size - 1, bitMask, shiftRightAmount, false );
else insertionSortSimilarToSTLnoSelfAssignment( a, a_size );
}
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.
