What algorithms are used in C++11 std::sort in different STL implementations?
algorithm, c++, c++11, sorting, stl
Solution
Browsing the online sources for libstdc++ and libc++, one can see that both libraries use the full gamut of the well-known sorting algorithms from an intro-sort main loop:
For `std::sort`, there is a helper routine for `insertion_sort` (an `O(N^2)` algorithm but with a good scaling constant to make it competitive for small sequences), plus some special casing for sub-sequences of 0, 1, 2, and 3 elements.
For `std::partial_sort`, both libraries use a version of `heap_sort` (`O(N log N)` in general), because that method has a nice invariant that it keeps a sorted subsequence (it typically has a larger scaling constant to make it more expensive for full sorting).
For `std::nth_element`, there is a helper routine for `selection_sort` (again an O(N^2) algorithm with a good sclaing constant to make it competitive for small sequences). For regular sorting `insertion_sort` usually dominates `selection_sort`, but for `nth_element` the invariant of having the smallest elements perfectly matches the behavior of `selection_sort`.
Problem
The C++11 standard guarantees that `std::sort` has O(n logn) complexity in the worst case. This is different from the average-case guarantee in C++98/03, where `std::sort` could be implemented with Quicksort (maybe combined with insertion sort for small n), which has O(n^2) in the worst case (for some specific input, such as sorted input). Were there any changes in `std::sort` implementations in different STL libraries? How is C++11's `std::sort` implemented in different STLs?