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

Question

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

如果它引用每个实现的引用，答案会更有用。

Answer 1

首先:编译器不提供std::sort的任何实现。虽然传统上每个编译器都预先打包了一个标准库实现(它严重依赖于编译器的内置)，但理论上您可以将一个实现换成另一个。一个很好的例子是 Clang 编译 libstdc++(传统上使用 gcc 打包)和 libc++(全新)。

现在已经不碍事了……

std::sort 传统上被实现为 intro-sort .从高层次的角度来看，这意味着一个相对标准的快速排序实现(通过一些中值探测来避免 O(n²) 最坏的情况)加上小输入的插入排序例程。然而，libc++ 实现略有不同并且更接近于 TimSort:它检测输入中已经排序的序列并避免再次对它们进行排序，从而导致在完全排序的输入上出现 O(n) 行为。它还使用优化的 sorting networks用于小输入。

另一方面，

std::stable_sort 本质上更复杂。这可以从标准的措辞中推断出来:复杂度是 O(n log n) if 可以分配足够的额外内存(提示 merge-sort) ，但如果不是，则退化为 O(n log² n)。