3 ms·
Why doesn't the STL switch to the hybrid sorting approach?
by imaginenore 10y ago
Why 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).
- wnesensohn 10y agoNo, f = O(n log n) means that f doesn't grow significantly faster than n log n. That is true for f = n log n, but it's also true for f = n. The "or better" is implicit by using big-O. Note that this wouldn't be true if the standard said that it has to be Θ(n log n).
- dietbacon 10y agoBig O complexity is an upper bound. If something is O(1) it's also O(n) and O(n!), since it's an upper bound.
- dom0 10y ago"the" STL?
- iherbig 10y agoSTL means "standard template library." It's perfectly reasonable to say "the standard template library."
- fooker 10y agoThere are several compatible and competing implementations of the C++ standard library.
- FlorianRappl 10y agoI think the author just wanted to point out that "the" STL is not valid / accurate here; while the interface and behavior is defined, the implementation is afaik still vendor specific, e.g., the implementation in GCC may be different from the one provided by Microsoft.
- tveita 10y agoThe STL sort uses operator<, so they can't implement it as radix sort without changing the interface. Maybe they could manage to special case it for some fundamental types, but most likely they'd need to add a new function, like for stable_sort.