STL sort()详解

函数原型（stl_algo.h）

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
  if (first != last) {
    __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
    __final_insertion_sort(first, last);
  }
}

template <class RandomAccessIterator, class Compare>
inline void sort(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp) {
  if (first != last) {
    __introsort_loop(first, last, value_type(first), __lg(last - first) * 2,
                     comp);
    __final_insertion_sort(first, last, comp);
  }
}

• 序列式容器只有vector、array（C++11起）、deque和string(因为string本质上是一个字符的vector)的迭代器类型是RandomAccessIterator，用到这个sort()；

• 对于像list这样的双向链表容器，由于其只提供双向迭代器，所以不能直接使用sort()算法。但是，你可以先将list的内容复制到vector或deque中，然后排序，最后再（如果需要的话）将结果复制回list。

• 对于关联容器（如set、multiset、map、multimap），它们内部已经是有序的，所以不需要（也不能）使用sort()进行排序。但是，你可以通过提供自定义的比较函数或函数对象来改变它们的排序顺序

策略

一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。

当数据量较大时采用快速排序，分段递归。

而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。