6 ms·
It might just be faster because the author is comparing their hybrid radix sort implementation to std::sort (which is comparison-based). Would be more valid to
by testerofwaters 10y ago
It might just be faster because the author is comparing their hybrid radix sort implementation to std::sort (which is comparison-based).
Would be more valid to compare to Boost's "spreadsort" which is similarly a hybrid radix sort algorithm (and also outperforms std::sort).
- d33 10y agoI had a feeling that O(N) is pretty impossible for the general use case.
- raverbashing 10y agoI think there's a (provable) mathematical impossibility to have a general O(N) sorting algorithm Basically, how many elements do you have to move in a list of N elements to end up with one of the possible orderings
- maweki 10y agoYou only ever have to move every element once to get a (pre-known) permutation that represents the sorted list. The problem is the information in a permutation (n! possible orderings) and one can only ever "throw away" half of them on every comparison, leading to log_2(n!) or nlog(n).
- Xorlev 10y agoIt's not impossible to have a O(N) sorting algorithm if you add more constraints, e.g. use operations other than comparisons. Most people would be fine with a hybrid radix sort for day to day use.
- beagle3 10y agoIt is impossible for comparison-based sorts; sketch of proof: there are N! different arrangements. sorting is equivalent to figuring which one of those N! arrangements we are seeing. In the worst case, each binary comparison can reduce at most, 50% of the search space. Hence the worst case may need log_2(N!) comparisons, which is O(N log N) However, it might be possible if comparisons are not essential - e.g. radix sort is (with some assumptions) O(N)
- imaginenore 10y agoWhy doesn't the STL switch to the hybrid sorting approach?
- sclangdon 10y agoSTL does use hybrid sorting. It is usually implemented as an introsort, which begins with a quicksort and switches to heapsort based on the number of elements to be sorted.
- imaginenore 10y agoSorry if that wasn't clear. I'm asking why don't they switch to the hybrid sort similar to Boost's, since it's known to be faster for most cases?
- sanxiyn 10y agoThey probably should. After all Boost is often a staging area for C++ standard library.
- adrianN 10y agoAFAIK the STL is free to use any algorithm they want as long as it's O(n log n).
- niftich 10y agoThis is correct. The C++ standard specifies that sort must have a big-O complexity of n log(n). This can be seen on pdf page 925 of this working draft from 2014 [1]. [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n429...
- sqeaky 10y agoSo providing a faster sort would be a violation? The standard doesn't seem to say "or better" here, but I know that in other places it does (or least used to say something similar).