Radix Sort Revisited
Although the standard Radix Sort doesn’t work very well with floating point values, this is something actually very easy to fix. In this little article I will review the standard Radix Sort algorithm, and enhance it so that:
- it sorts negative floats as well
- it has reduced complexity for bytes and words
- it uses temporal coherence
- it supports sorting on multiple keys
[…]
A Radix Sort is an apparently bizarre sort routine which manages to sort values without actually performing any comparisons on input data. That’s why this sort routine breaks the theoretical lower bound of the O(N*logN) complexity, which only applies for comparison-based sorts. Radix is O(k*N), with k = 4 most of the time, and although this is not an in-place sort (i.e. it uses extra storage) it is so much faster than any other sorting methods it has become a very popular way of sorting data.
