STL中的sort并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归；如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序；一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。
阈值(threshold)
从效率的角度来看,当元素数量很少的时候(例如只有十来个),使用快排这样比较复杂的算法是不太划算的,小数据量的情况下,插入排序也可能会快与快排,因为快排会产生的很多的函数递归调用.
final insertion sort
对于几近排序但是尚未完成的序列,插入排序的表现非常好,所以我们在快排到了序列比较短的时候,改用插入排序而不是彻底排好序(从效率的角度考虑).
introsort
不当的枢轴选择,导致不当的分割,导致快排恶化为O(N^2).而introsort则没这个问题,当分割没有问题时,它的表现和三点中值快排完全相同,但是当分割行为有恶化为二次行为的倾向时,能够自我侦测,转而使用Heap Sort,使效率维持在O(NLogN),又比一开始就使用Heap Sort来的好.
template <class _RandomAccessIter>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
_LessThanComparable);
if (__first != __last) {
__introsort_loop(__first, __last,
__VALUE_TYPE(__first),
__lg(__last - __first) * 2);
__final_insertion_sort(__first, __last);
}
}
其中，__introsort_loop便是内省式排序，其第三个参数中所调用的函数__lg()便是用来控制分割恶化情况，代码如下：
template <class Size>
inline Size __lg(Size n) {
Size k;
for (k = 0; n > 1; n >>= 1) ++k;
return k;
}
即求lg(n)（取下整），意味着快速排序的递归调用最多 2*lg(n) 层。
内省式排序算法如下：
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;
}
}
首先判断元素规模是否大于阀值__stl_threshold，__stl_threshold是一个常整形的全局变量，值为16，表示若元素规模小于等于16，则结束内省式排序算法，返回sort函数，改用插入排序。 若元素规模大于__stl_threshold，则判断递归调用深度是否超过限制。若已经到达最大限制层次的递归调用，则改用堆排序。代码中的partial_sort即用堆排序实现。 若没有超过递归调用深度，则调用函数__unguarded_partition()对当前元素做一趟快速排序，并返回枢轴位置。__unguarded_partition()函数采用的便是上面所讲的使用两个迭代器的方法，代码如下：
template <class _RandomAccessIter, class _Tp>
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
_RandomAccessIter __last,
_Tp __pivot)
{
while (true) {
while (*__first < __pivot)
++__first;
--__last;
while (__pivot < *__last)
--__last;
if (!(__first < __last))
return __first;
iter_swap(__first, __last);
++__first;
}
}
经过一趟快速排序后，再递归对右半部分调用内省式排序算法。然后回到while循环，对左半部分进行排序。源码写法和我们一般的写法不同，但原理是一样的，需要注意。 递归上述过程，直到元素规模小于__stl_threshold，然后返回sort函数，对整个元素序列调用一次插入排序，此时序列中的元素已基本有序，所以插入排序也很快。至此，整个sort函数运行结束。