[vvanders]

This is one of those cases where O(...) notation belies the actual performance on real systems.

The big advantage of Radix sort is not O(wn), it's that Radix sort linearly accesses its values in memory. This means that you can take full advantage of DDR read speeds since the prefetcher will run ahead of your cache misses to get you the data(or if you're smart you can prefetch yourself).

DDR fetch speeds are on the order of hundreds to thousands of cycles and that's where Radix's performance gain comes from.

[alecco]

Yeah, BigO is kind of dumb outside CS classes and interview questions. A Ludic Fallacy! Real top sorting records are most often based on radix (GPU) and merge (CPU+SIMD).