What algorithms do popular C++ compilers use for std::sort and std::stable_sort?

Question

What algorithms do popular C++ compilers use for std::sort and std::stable_sort? I know the standard only gives certain performance requirements, but I'd like to know which algorithms popular implementations use in practice.

The answer would be more useful if it cited references for each implementation.

Answer 1

First of all: the compilers do not provide any implementation of std::sort. Whilst traditionally each compiler comes prepackaged with a Standard Library implementation (which heavily relies on compilers' built-ins) you could in theory swap one implementation for another. One very good example is that Clang compiles both libstdc++ (traditionally packaged with gcc) and libc++ (brand new).

Now that this is out of the way...

std::sort has traditionally been implemented as an intro-sort. From a high-level point of view it means a relatively standard quick-sort implementation (with some median probing to avoid a O(n²) worst case) coupled with an insertion sort routine for small inputs. libc++ implementation however is slightly different and closer to TimSort: it detects already sorted sequences in the inputs and avoid sorting them again, leading to an O(n) behavior on fully sorted input. It also uses optimized sorting networks for small inputs.

std::stable_sort on the other hand is more complicated by nature. This can be extrapolated from the very wording of the Standard: the complexity is O(n log n) if sufficient additional memory can be allocated (hinting at a merge-sort), but degenerates to O(n log² n) if not.