3 ms·
C++ standard library implementations use introsort, so they never hit quicksort worst case.
by gpderetta 7y ago
C++ standard library implementations use introsort, so they never hit quicksort worst case.
- KerrickStaley 7y agostd::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 https://en.cppreference.com/w/cpp/algorithm/sort).
- gpderetta 7y agoIt 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.