4 ms·

Sure thing: http://en.wikipedia.org/wiki/Radix_sort http://en.wikipedia.org/wiki/Radix_sort

vvanders 12y ago
+1 Radix will destroy nlogn(sometimes by multiple orders of magnitude) for any data set that you can fit in memory(and with the radix size tuned for your appropriate cache line length). Never underestimate the strength of the prefetcher and using the correct data access patterns.
alecco 12y ago
Radix sort is amazing, but it's kinda O(n log n), see https://en.wikipedia.org/wiki/Radix_sort#Efficiency https://en.wikipedia.org/wiki/Radix_sort#Efficiency > Radix sort complexity is O(wn) for n keys which are integers of > word size w. Sometimes w is presented as a constant, which would > make radix sort better (for sufficiently large n) than the best > comparison-based sorting algorithms, which all perform O(n log n) > comparisons to sort n keys. However, in general w cannot be > considered a constant: if all n keys are distinct, then w has to > be at least log n for a random-access machine to be able to store > them in memory, which gives at best a time complexity O(n log n).[2] > That would seem to make radix sort at most equally efficient as the > best comparison-based sorts (and worse if keys are much longer than > log n).
- vvanders 12y ago
  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 11y ago
    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).

+1 Radix will destroy nlogn(sometimes by multiple orders of magnitude) for any data set that you can fit in memory(and with the radix size tuned for your appropriate cache line length). Never underestimate the strength of the prefetcher and using the correct data access patterns.

alecco 12y ago

Radix sort is amazing, but it's kinda O(n log n), see https://en.wikipedia.org/wiki/Radix_sort#Efficiency https://en.wikipedia.org/wiki/Radix_sort#Efficiency > Radix sort complexity is O(wn) for n keys which are integers of > word size w. Sometimes w is presented as a constant, which would > make radix sort better (for sufficiently large n) than the best > comparison-based sorting algorithms, which all perform O(n log n) > comparisons to sort n keys. However, in general w cannot be > considered a constant: if all n keys are distinct, then w has to > be at least log n for a random-access machine to be able to store > them in memory, which gives at best a time complexity O(n log n).[2] > That would seem to make radix sort at most equally efficient as the > best comparison-based sorts (and worse if keys are much longer than > log n).

vvanders 12y ago
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 11y ago
  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).