做流行的C ++编译器使用的std ::排序和std :: stable_sort什么算法？我知道这个标准只给出了一定的性能要求，但我想知道哪些算法实现普及在实践中使用。

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.

推荐答案

首先：编译器不提供的任意的实施的std ::的那种。虽然传统上每个编译器自带prepackaged一个标准库实现（这很大程度上依赖于编译器的内置插件），理论上你可以换一个实现另一个。一个很好的例子是，铛编译两者的libstdc ++（传统包装与海湾合作委员会）和libc中++（全新）。

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 ::排序传统上被实现为的介绍排序的。从一个高层次的点表示一个相对标准快速排序执行（与一些位数探测，以避免为O（n 2 ）最坏情况）加上对小输入的插入排序例程。的libc ++实现但略有不同，更接近TimSort：它检测到已经排序在输入序列，并避免再次对它们进行排序，从而为O（n）的完全分类的输入行为。它还使用优化排序网络的投入较小。

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 sort networks for small inputs.

的std :: stable_sort ，另一方面是性质上更加复杂。这可以从标准的十分措辞推断：复杂性是O（n log n）的如果的足够的额外内存可分配（暗示在的合并排序的） ，而是退化为O（N日志 2 N）如果没有。

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.