### Signed

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

01111111_{b} 127

01111110_{b} 126

01111101_{b} 125

….

00000001_{b} 1

00000000_{b} 0

11111111_{b} -1

11111110_{b} -2

11111101_{b} -3

…

10000011_{b} -125

10000010_{b} -126

10000001_{b} -127

10000000_{b} -128

Note that the most-significant-bit (MSB) serves as the sign bit. However, its meaning is opposite of what is needed for sorting (see Algorithm Improvement through Performance Measurement: Part 2_ and this bit either needs to be inverted or processed using opposite sense. Listing 4 shows the implementation for signed number, from 8-bit to 64-bit.

// Listing 4 // Treats the first digit specially, but the rest of the digits as unsigned. template< class _Type, unsigned long PowerOfTwoRadix, unsigned long Log2ofPowerOfTwoRadix, long Threshold > inline void _RadixSort_Signed_PowerOf2Radix_1( _Type* a, long last, _Type bitMask, unsigned long shiftRightAmount ) { 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 { unsigned long digit = (unsigned long)logicalRightShift_ru( (_Type)( a[ _current ] & bitMask ),shiftRightAmount ); // extract the digit we are sorting based on digit ^= ( PowerOfTwoRadix >> 1 ); count[ digit ]++; } long startOfBin[ numberOfBins ], endOfBin[ numberOfBins ], nextBin; startOfBin[ 0 ] = endOfBin[ 0 ] = nextBin = 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; ) { unsigned long digit; _Type tmp = a[ _current ]; // get the compiler to recognize that a register can be used for the loop instead of a[_first] memory location while ( true ) { digit = (unsigned long)logicalRightShift_ru( (_Type)( tmp & bitMask ), shiftRightAmount ); // extract the digit we are sorting based on digit ^= ( PowerOfTwoRadix >> 1 ); if ( endOfBin[ digit ] == _current ) break; _swap( tmp, a[ endOfBin[ digit ]] ); endOfBin[ digit ]++; } a[ _current ] = tmp; endOfBin[ digit ]++; // leave the element at its location and grow the bin _current++; // advance the current pointer to the next element while( _current >= startOfBin[ nextBin ] && nextBin < numberOfBins ) nextBin++; while( endOfBin[ nextBin - 1 ] == startOfBin[ nextBin ] && nextBin < numberOfBins ) nextBin++; if ( _current < endOfBin[ nextBin - 1 ] ) _current = endOfBin[ nextBin - 1 ]; } bitMask = logicalRightShift( bitMask, Log2ofPowerOfTwoRadix ); if ( bitMask != 0 ) // end recursion when all the bits have been processes { if ( shiftRightAmount >= Log2ofPowerOfTwoRadix ) shiftRightAmount -= Log2ofPowerOfTwoRadix; else shiftRightAmount = 0; for( unsigned long i = 0; i < numberOfBins; i++ ) { long numberOfElements = endOfBin[ i ] - startOfBin[ i ]; if ( numberOfElements >= Threshold ) // currentOffset actually points to one beyond the bin _RadixSort_Unsigned_PowerOf2Radix_1< _Type, PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( &a[ startOfBin[ i ]], numberOfElements - 1, bitMask, shiftRightAmount ); else if ( numberOfElements >= 2 ) insertionSortSimilarToSTLnoSelfAssignment( &a[ startOfBin[ i ]], numberOfElements ); } } }

Two special steps are taken to treat signed numbers differently than unsigned, as shown here:

digit = (unsigned long)logicalRightShift_ru( (_Type)( tmp & bitMask ), shiftRightAmount ); digit ^= ( PowerOfTwoRadix >> 1 );

The first step performs a right shift of a signed number as if it was unsigned. The second step inverts the most-significant-bit. The rest of the code is identical to the initial iteration of unsigned implementation, except for another logical right shift of the bitMask. The rest of the recursive iterations are performed using the unsigned algorithm.

In Tables 9 through 12, measurements show a performance degradation of a few percent due to the need to invert the MSB of the first digit. This overhead gets smaller as the element size increases. The rest of the performance characteristics match those of the unsigned implementations. Note that Intel IPP does not implement signed 8-bit or 64-bit integer versions of sorting.