3 ms·
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 guara
by KerrickStaley 7y ago
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 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.