Re:Bjarne Stroustrup Answers C++ Questions
by gpderetta on Tuesday October 15, 2019 @09:07AM
(#21257936)
C++ standard library implementations use introsort, so they never hit quicksort worst case.
[ Parent
| on HN ]
Re:Bjarne Stroustrup Answers C++ Questions
by KerrickStaley on Tuesday October 15, 2019 @02:12PM
(#21261729)
std::sort is not required to use any specific algorithm; it only guarantees that it uses an O(N log N) worst-case algorithm (since C++11, before C++11 the guarantee was average-case O(N log N), see https://en.cppreference.com/w/cpp/algorithm/sort).
Re:Bjarne Stroustrup Answers C++ Questions
by gpderetta on Tuesday October 15, 2019 @03:35PM
(#21262739)
It is not guaranteed, but all the libraries do. In fact in the past the bound was O(N²) as the expectation was that quick sort would be the default choice, but because all implementations used introsort, the bound was thighened.