在不同的STL实现中，哪些algorithm用于C ++ 11 std :: sort？
C ++ 11标准保证std::sort 在最坏的情况下具有O（n logn）的复杂性 。 这与C ++ 98/03中的平均保证有所不同，在这种情况下 std::sort可以用Quicksort来实现（可能与小n的插入sorting相结合），在最坏的情况下有O（n ^ 2） （对于一些特定的input，例如sorting的input）。
不同的STL库中的std::sort实现有没有改变？ C ++ 11的std::sort如何在不同的STL中实现？
浏览libstdc ++和libc ++的在线资源，可以看到两个库都使用来自intro-sort主循环的众所周知的sortingalgorithm：
对于std::sort ，有一个辅助函数用于insertion_sort （一个O(N^2)algorithm，但是有一个很好的比例常数，以使它在小序列上具有竞争力），加上一些特殊的子序列0,1， 2和3个元素。
对于std::partial_sort ，两个库一般都使用heap_sort （ O(N log N) ）版本，因为该方法有一个很好的不变性，保持一个已sorting的子序列（它通常具有更大的缩放常量，使其更加昂贵为了完整的分类）。
对于std::nth_element ，有一个用于selection_sort的辅助例程（又一个O（N ^ 2）algorithm，具有良好的sclaing常量，使其在小序列中具有竞争力）。 对于常规的sorting， insertion_sort nth_element通常支配selection_sort ，但对于nth_element ，具有最小元素的不variables完全匹配selection_sort的行为。
问题是， STL怎么说std::sort最坏的情况是O（N log（N）） ，即使它本质上是一个QuickSort 。 STL的sorting是IntroSort 。 IntroSort本质上是一个QuickSort，所引入的差异改变了最糟糕的情况下的复杂性。
QuickSort最坏的情况是O（N ^ 2）
你select什么分区，存在一个QuickSort将在O（N ^ 2）上运行的序列。 您select的分区只会降低最坏情况发生的概率。 （ 随机枢轴select ，三位中间值等 ）
编辑：感谢@ maxim1000的更正。 枢轴selectalgorithm的快速sorting中间值Medians具有O（N log（N））最坏的情况下的复杂性，但是由于它引入的开销，它在实践中不被使用。 这说明了selectalgorithm有多好，理论上可以通过枢纽select来改变最坏情况下的复杂度。
IntroSort做什么？
IntroSort限制了QuickSort的分支。 这是最重要的一点，限制是2 * （log N） 。 当达到限制时，IntroSort可以使用具有最坏情况复杂度O（N log（N））的任何sortingalgorithm。
当O（log N）子问题出现时，分支停止。 我们可以解决每个子问题O（n log n）。 （小写n表示子问题的大小）。
（n log n）之和现在是我们最糟糕的情况。
对于QuickSort最糟糕的情况; 假设我们有一个已经sorting的数组，并且我们总是select这个数组中的第一个元素作为枢轴。 在每一次迭代中，我们只摆脱了第一个元素。 如果我们这样走到最后，显然是O（N ^ 2） 。 使用IntroSort时，我们停止QuickSort，当我们到达深度日志（N）时 ，我们使用HeapSort来处理剩余的未sorting数组。
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实现源代码在这里 。 Sortfunction在5461行。
更正： * Microsoft .NET *sorting实现是自2012年以来的IntroSort。相关信息在这里 。
