流行的 C++ 编译器对 std::sort 和 std::stable_sort 使用什么算法？

Question

流行的 C++ 编译器对 std::sort 和 std::stable_sort 使用什么算法？我知道该标准只给出了某些性能要求，但我想知道流行的实现在实践中使用哪些算法。

如果答案引用了每个实现的参考资料，将会更有用。

Answer 1

首先：编译器不提供 std::sort 的

any

实现。虽然传统上每个编译器都预先打包了一个标准库实现（它严重依赖于编译器的内置函数），但理论上您可以将一种实现替换为另一种实现。一个很好的例子是 Clang 编译 libstdc++（传统上用 gcc 打包）和 libc++（全新）。

现在这已经不成问题了...

std::sort

传统上被实现为介绍排序。从高层的角度来看，这意味着相对标准的快速排序实现（通过一些中值探测来避免 O(n²) 最坏情况）以及针对小输入的插入排序例程。然而，libc++ 实现略有不同，并且更接近 TimSort：它检测输入中已排序的序列并避免再次对它们进行排序，从而导致完全排序输入上的 O(n) 行为。它还针对小输入使用优化的排序网络。

另一方面，

std::stable_sort

本质上更加复杂。这可以从标准的措辞中推断出来：复杂度为 O(n log n) if 可以分配足够的额外内存（暗示 merge-sort），但退化为 O(n log² n) 如果没有。

Answer 2

如果我们以 gcc 为例，我们会发现它对于

std::sort

是内插排序，对于

std::stable_sort

是归并排序。

如果您仔细阅读 libc++ 代码，您会发现如果范围足够大，它也会对

std::stable_sort

使用归并排序。

您还应该注意的一件事是，虽然一般方法始终是上述方法之一，但它们都针对各种特殊情况进行了高度优化。