Can Radix Sort be modified for signed ints and/or floats?

Question

A few months ago I learned about the magic that allows radix sort to run in O(n) time and space. Most tutorials on radix sort say it is useful for very large collections where the key values fall inside a defined range. They then go on to say that it's really only reasonable when sorting unsigned integers. The reasons made sense.

I also recently learned about the IEEE floating point specification and it got me thinking about about 2s-compliment signed ints at the same time. In both cases the MSB of the value represents the sign of the value, with 1 indicating a negative and 0 indicating positive. That means that an int or float with a MSB of 1 should go before another with a MSB of 0.

With that in mind, couldn't signed ints or floats be sorted with the following algorithm?

1. Run Radix Sort using the raw bytes. This takes O(n). Let p be the count of positive numbers in the array. The array now has two parts.

• array[0:p] is a sorted array of the positive values.
• array[p:n] is a reverse sorted array of the negative values.

2. Initialize pointers i = 0; j = n - 1 and the final return array of length n.
3. While msd(array[j])==1, copy array[j] to the final array and decrement j. This takes O(n-p)
4. While i < j, copy array[i] to the final array and increment i. This takes O(p)
5. The final array is now sorted.

If this works it runs in O(n) + O(n-p) + O(p) = O(n) time. We can reuse the second array from the radix sort, which used O(n) space.

This feels like a relatively easy way to extend Radix sort to signed values. Does it not work? What am I missing?

Answer 1

Radixsort for signed integers is probably considered a folklore result. Take a look at Exercises 8 and 9 of Section 5.2.5 of Knuth's book The Art of Computer Programming: Volume 3: Sorting and Searching: Sorting and Searching, Volume 3.