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.
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(n2) 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 log2 n) if not.
O(n lg^2 n) "mergesort" for a while now. It's definitely not a usual mergesort since it doesn't use the extra memory - what can it be?
Introsort algorithm, which also includes pseudocode for the algorithm, en.wikipedia.org/wiki/IntrosortIf we take gcc as an example we see that it is introsort for std::sort and mergesort for std::stable_sort.
If you wade through the libc++ code you will see that it also uses mergesort for std::stable_sort if the range is big enough.
One thing you should also note is that while the general approach is always one of the above mentioned ones, they are all highly optimized for various special cases.
