目录
STL的sort函数非常常用，不同的STL版本有不同的实现方式，本文就来说一下SGI STL中是如何实现sort函数的。
sort函数所采用的排序方法并非是“一种”，而是“多种”排序算法的“混合物”。在SGI STL的版本中，对一个序列调用sort函数，那么这个序列可能会经历插入排序、快速排序和堆排序，其中最为核心的是快速排序。每种排序方式都是在特定情况下使用的，搭配使用从而更加高效。
由于需要使用到这么多的排序方式，因此调用sort函数的容器必须支持“Random access iterator”（如果不能随机访问，那么快排选取枢轴会受到极大限制），即随机访问迭代器（即支持迭代器++、--和+=、-=）。在众多STL容器中，由于红黑树的迭代器是一个双向迭代器（仅支持++、--），hashtable的迭代器是一个前向迭代器（仅支持++），因此set、map(二者本身就有序)、hash_set和hash_map以及相应的multixxx都不适用于sort函数；queue和stack不允许排序，而list的迭代器是一个双向迭代器，slist的迭代器是一个前向迭代器，因此STL容器中适用sort函数的只有vector和deque。
插入排序的思想，就是在排序过程中把整个序列分为有序子序列和无序子序列，初始状况下有序子序列中只含有第一个元素。接着从第二个元素开始遍历，对于每个当前遍历的元素X，都会在其左侧的有序子序列中寻找到第一个小于X的元素Y，在寻找过程中，比X大的元素会与X交换位置，找到Y后把X插入Y的后面。整个排序过程中，当前遍历的元素的左边就是有序子序列，右边及它自身则为无序子序列。插入排序过程如下所示：
从插入排序的过程来看可以知道，插入排序的平均时间复杂度为O(N^2)，它取决于每个元素往回遍历时“何时才能找到第一个小于它的元素”。如果元素的数量比较少，那么显然插入排序会趋向于O(N)。
快速排序的思想，就是在序列中寻找一个枢轴，每一次遍历时可以让小于或等于枢轴的元素放在一边，而大于或等于枢轴的元素放在另外一边。然后再进行递归，对子区间进行快速排序，最终得到有序序列。 快速排序的平均时间复杂度为O(NlogN)，影响其效率的关键在于枢轴的选取，如果枢轴选取不当，那么可能最终分隔出来的两个区间一个太长一个太短，此时快速排序就会趋向于O(N^2)。实际上，序列无序比有序更有益于快速排序，序列本身越有序，那么快速排序退化为O(N^2)的概率就更大，序列越随机无序越好。
堆排序也是一种平均时间复杂度为O(NlogN)的排序算法。不过相较于快速排序的一般情况，堆排序每插入一个数据都需要进行调整堆，这样就使得堆排序过程中元素的比较、交换过程比快速排序更多，虽然也是O(NlogN)级别，但在平均情况下还是略逊于快速排序。不过堆排序的好处是：可以实时插入数据来排序，并且最差情况也是O(NlogN)。
从工业应用上来说，如果只是为了排序，那么快速排序在大多数情况下都是表现最好的一种排序算法，也是最常用的排序算法。不过为了精益求精，SGI STL在使用快速排序的同时，还使用插入排序和堆排序来尽量避免快速排序可能出现的问题。
基于以上三种排序算法的特点，SGI STL中的sort函数有以下策略：
1.如果序列元素数量较少，那么应该采用插入排序。
如前所述，插入排序在元素较少的情况下时间复杂度会趋向于O(N)，而快速排序在元素较少的情况下，也更容易出现O(NlogN)向O(N^2)退化的情况，除此之外，快速排序内部是会递归排序的，这是无可避免的，在元素较少的情况下，多次递归调用所影响的效率降低也是值得考虑的。介于此，SGI STL认为，在元素较少的情况下，插入排序会比快速排序表现更好。
那么，如何去衡量“元素较少”呢？这在不同版本的STL中有不同的规定。
在SGI STL中，通过const变量__stl_threshold来定义这个值为16：
而在VS2013 STL中，则通过const变量_ISORT_MAX来定义这个值为32：
可见，在不同版本的STL中，对于这个值的定义是不同的。当序列元素数量小于该值，就会使用插入排序。
2.在快速排序过程中，如果递归子区间的元素个数较少，那么就停止快速排序，转而使用插入排序。
这一点实际上和第1点是类似的。个人认为这里主要是考虑到对于小数组来说，插入排序与快速排序的差别不会很大，而快排由于本身还需要有递归的消耗，所以插入排序在小数组的情况下效果会好一些。
3.快速排序递归深度不宜过深，过深则用堆排序来替代。
快速排序是一个递归的过程，越往下递归，子区间越小，递归消耗就越大，还可能造成栈溢出。但是如果此时子区间还没有达到插入排序的阈值该怎么办呢？既然此时不能再从子区间元素数量来衡量，那么就可以从递归深度来衡量，这样还可以避免递归栈溢出。
那么如何去衡量“递归深度”呢？SGI STL用2*log(N)来作为快速排序的最大递归深度。举个例子，40个元素，那么快速排序递归的最大深度就是2*log(40)=2*5=10，也就是说，如果快速排序递归了10次，还没达到插入排序的阈值，那么就不应当再使用快速排序了，此时就会转为使用堆排序，对该子区间的元素进行排序。使用堆排序来代替的好处是可以让时间复杂度保持在O(NlogN)。
下面来看看sort函数内部是如何实现的。
sort函数源码如下：(以默认的升序为例，不考虑比较器的sort)
template <class _RandomAccessIter>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
......
if (__first != __last) {
__introsort_loop(__first, __last,
__VALUE_TYPE(__first),
__lg(__last - __first) * 2);//此时序列已经变为基本有序
__final_insertion_sort(__first, __last);
}
}在sort函数中，调用了两个函数，一个是introsort_loop，一个是final_insertion_sort。
这里的introsort就是内省排序，是David R.Musser于1996年提出的一种混合式排序算法。它也是上面第3点策略的体现。该函数定义如下：
template <class _RandomAccessIter, class _Tp, class _Size>
void __introsort_loop(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*,
_Size __depth_limit)
{
while (__last - __first > __stl_threshold) {
if (__depth_limit == 0) {//到达递归深度限制，就使用堆排序
partial_sort(__first, __last, __last);
return;
}
--__depth_limit;
_RandomAccessIter __cut =
__unguarded_partition(__first, __last,
_Tp(__median(*__first,
*(__first + (__last - __first)/2),
*(__last - 1))));//通过快排找到分割点
__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);//对分割点右边的部分继续快排
__last = __cut;//分割点左边的部分进入下一个循环，左边的部分一定小于等于右边的部分
}
}这个函数的第四个参数是depth_limit，也就是递归深度限制，可以看到，每次调用该函数的时候，depth_limit都会-1，然后作为递归调用introsort_loop的第四个参数，如果depth_limit为0，那么说明到达了最大的递归深度，此时就会调用partial_sort，就是堆排序来对该区间的元素进行排序。introsort的核心思想就是如此，sort函数的第3点策略也体现于此。再来说下其它部分。
__unguarded_partition就是快速排序的体现，传入的前两个参数是排序区间，第三个参数是枢轴值，SGI STL选用区间第一个、中间的和最后一个元素三者大小排序中间的那个元素作为枢轴，这样的好处是避免枢轴直接是最大值或最小值而导致快速排序退化为冒泡排序。__unguarded_partition函数的返回值交给cut，它是分割点，即在cut左边的元素都不大于刚才选取的枢轴值，cut右边的元素都不小于刚才选取的枢轴值。
得到了cut，就相当于快速排序结束了一轮，此时再次递归调用introsort_loop来对右子区间进行快速排序。而左子区间的快排则直接通过当前的循环进行，把cut作为左子区间的右端点，再次进行introsort_loop。
值得注意的是这个循环的条件，是__last-first>stl_threshold，也就是说区间中的元素要超过stl_threshold才能继续进行快速排序，这个stl_threshold就是前面说的插入排序的阈值，如果小于或等于这个阈值，就会退出该循环。
退出这个循环后会做什么呢？
接下来就是调用__final_insertion_sort函数，从函数名就知道，插入排序就执行于此，该函数定义如下：
template <class _RandomAccessIter>
void __final_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
if (__last - __first > __stl_threshold) {//将序列分为两段来插入排序效果会更好
__insertion_sort(__first, __first + __stl_threshold);
__unguarded_insertion_sort(__first + __stl_threshold, __last);
}
else
__insertion_sort(__first, __last);
}先来想一下什么时候会调用该函数：一种是序列本身元素数量就少于stl_threshold，那么直接执行__final_insertion_sort，这种情况属于序列元素较少，此时应该直接进行插入排序，属于sort函数的第1条策略；第二种是快速排序递归后子区间元素数量少于stl_threshold，此时相当于对“基本有序”的序列进行插入排序，这种属于sort函数的第2条策略。
在第一种情况下，显然就会直接执行else下的__insertion_sort，这个函数实际上就是进行插入排序，没别的。
值得注意的是在第二种情况下，进入if中，会把序列分为两段来进行插入排序。之所以这样，是因为在经过快速排序后，序列中的前面stl_threshold元素整体必定是小于后面的元素的，此时对这两段分别排序肯定比一起排序更好（序列越短越利于插入排序，但是这也要建立在分开插入排序后整体依然是有序的前提，而这里的stl_threshold就保证了这一点）。