2 ms·
Definitely not quick sort -- getting it to be an O(n log n) worst case is very hard, and usually enough to disqualify it as "quick" (if such a title is ever war
by beagle3 14y ago
Definitely not quick sort -- getting it to be an O(n log n) worst case is very hard, and usually enough to disqualify it as "quick" (if such a title is ever warranted, given the n^2 worst case).
Any reason why specifically radix sort, rather than (say) TimSort (super-optimized merge-sort), which has better memory locality than radix sort, and can accommodate non-lexicographic orders (useful for e.g. non-normalized unicode) unlike radix sort?
- saurik 14y agoThe data types being discussed here are 32-bit integers and floating point numbers; radix sort can be made downright epic for these types. http://stereopsis.com/radix.html http://stereopsis.com/radix.html Also, the reason I mention quick sort is that that is the algorithm the EXPLAIN output of PostgreSQL claims it uses: I agree that for more complex types or complex comparison functions radix sort will not work, and agree as well that some other sorting algorithm may be preferred to what PostgreSQL currently does.