STL的sort()算法，数据量大时采用Quick Sort，分段递归排序，一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来过大的额外负荷，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort。本文先分别介绍这个三个Sort，再整合分析STL sort算法(以上三种算法的综合) -- Introspective Sorting(内省式排序)。

指导博文

指导博文2

为什么是Insertion Sort，而不是Bubble Sort。

选择排序(Selection sort)，插入排序(Insertion Sort)，冒泡排序(Bubble Sort)。这三个排序是初学者必须知道的三个基本排序方式，且他们速度都不快 -- O(N^2)。选择排序就不说了，最好情况复杂度也得O(N^2)，且还是个不稳定的排序算法，直接淘汰。

可冒泡排序和插入排序相比较呢？

首先，他们都是稳定的排序算法，且最好情况下都是O(N^2)。那么我就来对他们的比较次数和移动元素次数做一次对比（最好情况下），如下：

插入排序：比较次数N-1，移动元素次数2N-1。

冒泡排序：比较次数N-1，无需移动元素。(注：我所说的冒泡排序在最基本的冒泡排序基础上还利用了一下旗帜的方式，即寻访完序列未发生数据交换时则表示排序已完成，无需再进行之后的比较与交换动作）

那么，这样看来冒泡岂不是是更快，我可以把上述的__final_insertion_sort()函数改成一个__final_bubble_sort()，把每个子序列分别进行冒泡排序，岂不是更好？

事实上，具体实现时，我才发现这个想法错了，因为写这么一个__final_bubble_sort()，我没有办法确定每个子序列的大小，可我还是不甘心呐，就把bubble_sort()插在__introsort_loop()最后，这样确实是每个子序列都用bubble_sort()又排序了一次，可是测试结果太惨了，由此可以看书Bubble Sort在“几近排序但尚未完成”的情况下是没多少改进作用的。

为什么不直接用Heap Sort

在算法导论课后西提2-2中又问了”冒泡排序和插入排序哪个更快“呢？

一般的人回答：“差不多吧，因为渐近时间都是O(n^2)”。

但是事实上不是这样的，插入排序的速度直接是逆序对的个数，而冒泡排序中执行“交换“的次数是逆序对的个数，因此冒泡排序执行的时间至少是逆序对的个数，因此插入排序的执行时间至少比冒泡排序快。

堆排序将所有的数据建成一个堆，最大的数据在堆顶，它不需要递归或者多维的暂存数组。算法最优最差都是O(NlogN)，不像快排，如果你人品够差还能恶化到O(N^2)。当数据量非常大时（百万数据），因为快排是使用递归设计算法的，还可能发出堆栈溢出错误呢。

那么为什么不直接用Heap Sort？或者说给一个最低元素阈值（__stl_threshold)时也给一个最大元素阈值（100W），即当元素数目超过这个值时，直接用Heap Sort，避免堆栈溢出呢？

对于第一个问题，我测试了一下，发现直接用Heap Sort，有时还没有Quick Sort快呢，查阅《算法导论》发现，原来虽然Quick和Heap的时间复杂性是一样的，但堆排序的常熟因子还是大些的，并且堆排序过程中重组堆其实也不是个省时的事。

VS2010版STL中的sort竟比我自己写的快这么多？

    首先，上文实现的这个Introsort是参照SGI STL写的，于是，我斗胆在VS2010中拿他与std:sort比了比快慢。于是就随机产生两个百万数据的vector用来测试。结果发现，VS中sort的速度竟是我的10倍以上的效率。顿时对微软萌生敬意，可是当我仔细翻看源码时.....

    原来，microsoft的sort并没有比sgi的sort快。只是在排序vector时，microsoft把vector的本质数据“萃取”出来了。即，取消了vector在++时的边界检查语句，把vector::iterator当指针一般使用。所以才在对vector排序时会比我自己写的introsort算法快那么多呢。