STL sort函数的内部实现

（1）在STL提供的各式各样的算法中，sort()是最复杂最庞大的一个。这个算法只接受RandomAccessIterators（随机存取迭代器），然后将区间内所有元素由小到大重新排列。第二个版本允许用户自己指定一个仿函数作为排序标准。

---

（2）对于关系型容器，底层自己采用有自动排序功能的RB-Tree，不需要用到sort算法，序列式容器中stack、queue和priority_queue是容器适配器，都有特别的出入口，不允许用户对其进行排序。剩下的vector、deque和list，前两者的迭代器属于RandomAccessIterators，适合用sort算法，list的迭代器则属于BidirectionIterators，不在STL标准之列的slist，其迭代器更是属于ForwardIterators，都不适合于sort算法。如果要对list或者slist排序，应该他们自己提供member function sort()。那么为什么泛型算法sort()一定要求RandomAccessIterators？

---

（3）STL的sort()算法，数据量大时采用Quick Sort，分段递归排序。一旦分段后的数据量小于某个阈值，为避免Quick Sort的递归调用带来过大的额外开销，就改用Insertion Sort（插入排序）。如果递归层次过深，还会改用Heap Sort。
（4）如果我们拿Insertion Sort来处理大数据量，其O(N^2)的复杂度无法令人接受。大数据量有更好的排序算法可供选择。快排是目前已知的最快的排序方法，平均复杂度为O(N log N),最坏情况O(N^2)。不过IntroSort（极其类似 median-of - three QuickSort的一种排序算法）可将最坏情况推进到O（NlogN），早期的STL sort算法都采用QuickSort，SGI STL已经改用IntroSort。 QuickSort的精神在于将大区间分割为小区间，分段排序，每一个小区间排序完成后串接起来大区间也就完成了排序。最坏的情况发生在分割时产生了一个空的子区间 - 那完全没有达到分割的预期效果。

---

（5）Median - of - Three（三点中值） 任何一个元素都可以被选来当做枢轴（pivot），但是其合适与否会影响快排的效率。为了避免元素当初输入时不够随机所带来的恶化效应，最理想最稳当的做法是去整个序列的头、尾、中央三个位置的元素，以其中值（median）作为数轴。这就叫median-of - three QuickSort，为了能够快速取出中央位置的元素，显然迭代器必须能够随机定位，亦即必须要是个RandomAccessIterators。
（6）阈值threshold 面对只有十来个元素的小型序列，用像QuickSort这样复杂而可能需要大量运算的快速排序似乎显得不划算。所以，在小数据量的情况下，InsertionSort也可能快过QuickSort，因为Quick会为了极小的子序列而产生许多的函数递归调用。 基于这种情况，适度评估序列的大小，然后决定采用InsertionSort还是QuickSort。

---

堆排序比较和交换次数比快速排序多，所以平均而言比快速排序慢，也就是常数因子比快速排序大，如果你需要的是“排序”，那么绝大多数场合都应该用快速排序而不是其它的O(nlogn)算法。

但有时候你要的不是“排序”，而是另外一些与排序相关的东西，比如最大/小的元素，topK之类，这时候堆排序的优势就出来了。用堆排序可以在N个元素中找到top K，时间复杂度是O(N log K)，空间复杂的是O(K)，而快速排序的空间复杂度是O(N)，也就是说，如果你要在很多元素中找很少几个top K的元素，或者在一个巨大的数据流里找到top K，快速排序是不合适的，堆排序更省地方。

另外一个适合用heap的场合是优先队列，需要在一组不停更新的数据中不停地找最大/小元素，快速排序也不合适。

此外merge sort之类算法虽说也是O(nlogn)，但一般都只在一些很特殊的场合才会用，比如N-way merge，可以把N个已经排好序的数据流合并成一个排好序的数据流，当然这个算法其实严格说并不能算是merge sort，只是用了其中的几个步骤，不过思路是一样的。

基于交换的排序常用的就这么几种（什么冒泡选择之类的你可以无视了），其它的不基于交换的排序比如radix sort、bucket sort之类由于应用场合比较特殊，一般很少用到。

std::sort的代码如下：

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 T, class Size>
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
    while (last - first > __stl_threshold) {
        if (depth_limit == 0) {
            partial_sort(first, last, last);
            return;
        }
        --depth_limit;
        RandomAccessIterator cut = __unguarded_partition
          (first, last, T(__median(*first, *(first + (last - first)/2),
                                   *(last - 1))));
        __introsort_loop(cut, last, value_type(first), depth_limit);
        last = cut;
    }
}

递归深度阈值

现在我们来关注循环条件和if语句。__introsort_loop的最后一个参数depth_limit是前面所提到的判断分割行为是否有恶化倾向的阈值，即允许递归的深度，调用者传递的值为2logN。注意看if语句，当递归次数超过阈值时，函数调用partial_sort，它便是堆排序:

template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
	RandomAccessIterator last, T*, Compare comp) {
	make_heap(first, middle, comp);
	for (RandomAccessIterator i = middle; i < last; ++i)
	if (comp(*i, *first))
		__pop_heap(first, middle, i, T(*i), comp, distance_type(first));
	sort_heap(first, middle, comp);
}

template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
	RandomAccessIterator middle,
	RandomAccessIterator last, Compare comp) {
	__partial_sort(first, middle, last, value_type(first), comp);
}

如前所述，此时采用堆排序可以将快速排序的效率从O(N2)提升到O(N logN)，杜绝了过度递归所带来的开销。堆排序结束之后直接结束当前递归。

template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
	RandomAccessIterator last,
	T pivot) {
	while (true) {
		while (*first < pivot) ++first;
		--last;
		while (pivot < *last) --last;
		if (!(first < last)) return first;
		iter_swap(first, last);
		++first;
	}
}

Insertion Sort（插入排序）
那么同样都是插入排序，__insertion_sort和__unguarded_insertion_sort有何不同，为什么叫unguarded？接下来看看STL的实现：（注：这里取得都是采用默认比较函数的版本）：

template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
	RandomAccessIterator next = last;
	--next;
	while (value < *next) {
		*last = *next;
		last = next;
		--next;
	}
	*last = value;
}

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first,
	RandomAccessIterator last, T*) {
	T value = *last;
	if (value < *first) {
		copy_backward(first, last, last + 1);
		*first = value;
	}
	else
		__unguarded_linear_insert(last, value);
}

template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
	if (first == last) return;
	for (RandomAccessIterator i = first + 1; i != last; ++i)
		__linear_insert(first, i, value_type(first));
}

__final_insertion_sort

template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first,
	RandomAccessIterator last) {
	if (last - first > __stl_threshold) {
		__insertion_sort(first, first + __stl_threshold);
		__unguarded_insertion_sort(first + __stl_threshold, last);
	}
	else
		__insertion_sort(first, last);
}
template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
	RandomAccessIterator last, T*) {
	for (RandomAccessIterator i = first; i != last; ++i)
		__unguarded_linear_insert(i, T(*i));
}

template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
	RandomAccessIterator last) {
	__unguarded_insertion_sort_aux(first, last, value_type(first));
}

附上详细地址：http://www.udpwork.com/item/12284.html