C 11标准保证std::sort在最坏的情况下具有O（n logn）复杂性。这与C 98/03中的平均值保证，其中std::sort可以使用QuickSort实现（也许与小N的插入排序结合），该n具有O（n^2）在最坏的情况下（对于某些特定输入，例如排序输入）。
不同STL库中的std::sort实现有任何变化吗？C 11的std::sort如何在不同的STL中实现？
问题是， stl 如何说 std::sort最坏情况是 o（n log（n）），即使它是本质上， QuickSort 。STL的排序是 Introsort 。插入本质上是QuickSort，差异引入了最坏情况的复杂性。
QuickSort最坏情况是O（n^2）
您选择的任何分区，都存在一个序列，即QuickSort将在 o（n^2）上运行。您选择的分区只会降低发生最坏情况的概率。（随机枢轴选择，三个中位数等）
编辑：感谢 @maxim1000 s校正。带有枢轴选择算法中值中位数的QuickSort具有 o（n log（n））最坏情况的复杂性，但是由于间接费用，它引入了它在实践中未使用。它显示了良好的选择算法如何通过理论上的枢轴选择来改变最坏情况的复杂性。
插入术有什么作用？
introsort限制了QuickSort的分支。这是最重要的一点，该限制是 2 * （log n）。当达到限制时，Introsort可以使用任何具有O（n log（n））最坏情况复杂性的排序算法。
当我们拥有O（log n）子问题时，分支会停止。我们可以解决每个子问题O（n log n）。（下情况n代表子问题大小）。
（n log n）的总和是我们最坏的情况，现在。
对于QuickSort的最坏情况；假设我们有一个已经排序的数组，并且我们始终选择此数组中的第一个元素作为枢轴。在每次迭代中，我们都只能摆脱第一个元素。如果我们以这种方式直到最后，那将是 o（n^2）。使用Introsort，我们停止了QuickSort，当我们达到深度 log（n）时，我们将使用 heapsort 用于其余的未分类数组。
16 -> 1 /**N**/
> 15 -> 1 /**N - 1**/
> 14 -> 1 /**N - 2**/
> 13 -> 1 /**N - log(N)**/
> 12 /**(HeapSort Now) (N - log(N)) log (N - log(N))**/
总结一下;
直到分支停止，N + (N - 1) + ... + (N - log(N))操作完成。我们可以简单地说N + (N - 1) + ... + (N - log(N)) < N log(N)。
heapsort部分是 (N - log(N)) log(N - log(N)) < N log(N)
总体复杂性< 2 N log(N)。
由于可以省略常数，因此 Introsort 的最坏情况是 o（n log（n））。
添加了信息： GCC STL实现源代码在这里。Sort功能在行 5461 。
校正： * microsoft .net .net *排序实现是自2012年以来的省级。相关信息在此。
浏览 libstdc 和 libc 的在线资源，人们都可以看到两个库都使用了众所周知的分类范围介绍主循环中的算法：
对于std::sort，insertion_sort有一个辅助程序（O(N^2)算法，但具有良好的缩放常数以使其具有竞争力的小序列），以及对于0、1、2和3个元素的一些特殊套管。
对于std::partial_sort，两个库都使用heap_sort的版本（通常是O(N log N)），因为该方法具有不变的不变性，可以保持分类的子序列（通常具有较大的缩放常数，可以使其更昂贵，以使其更昂贵）。
对于std::nth_element，selection_sort有一个辅助程序（再次是一种具有良好SCLA的常数的O（n^2）算法，可以使其对小序列具有竞争力）。对于常规排序insertion_sort通常主导selection_sort，但对于nth_element，具有最小元素的不变性与selection_sort的行为完全匹配。