STL算法之sort源码

总体上来说sort在快排基础上做了以下几点优化：

1. pivot选取，取区间的首，中间，尾部三点中值，避免快排算法恶化
2. 快排采用分而治之的思想，将待排序容器分为若干个区间，由于采用的时递归实现，当区间个数太多，导致效率下降。这里当区间大于lg(last - first) * 2时，采用堆排序来优化。
3. 最后，当区间元素个数小于16时，此时区间元素已大致有序，采用插入排序，时间复杂度可达到O(n);

std::sort的代码如下：

template 
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
    	// 执行快排
        __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);  // __lg(last - first) * 2	即为递归的深度限制
        //  执行插入排序
        __final_insertion_sort(first, last);
    }
}

__introsort_loop 实现

template 
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;
        // cut即为pivot
        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;
    }
}

__final_insertion_sort 实现

template 
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);
}