关于 MSVC STL 排序函数的研究笔记
自从八月打完电赛，就忙着找工作和考研，好久没更新博客了。
前一阵子在刷算法题的时候，忽然开始好奇STL中的排序算法是如何实现的。
于是就去研究了 MSVC STL 中的 ranges::sort 的实现。
源代码请看这里 MSVC STL
内省排序
首先需要明确的是，C++标准并未严格规定 sort() 的具体实现。于是主流编译器 MSVC 和 GCC 中都选择了 内省排序(Introsort) 作为其具体的实现方式。
所谓内省排序，是一种混合算法。主要采用快速排序和堆排序共同完成排序功能。
众所周知的是，这两种排序各有优缺点。例如快速排序并不稳定，时间复杂度最优是 $O(n\log{n})$ ，而最差为 $O(n_2)$ 。虽然堆排序能够稳定实现 $O(n\log{n})$ ，但是在操作效率上不如快速排序（例如快速排序有较高的缓存使用率）。
但如果将两种算法混合使用，先用快速排序尝试进行几轮的排序，若递归深度过深，就转而采用堆排序，从而规避两种排序的缺点，并结合两者的优点，进而达到最好的效率。
在 MSVC 所选用的实现中，就采用了这样的思路。不过进行了少许的改进，在排序范围较小的时候直接采用插入排序，进一步加快排序速度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| template <class _It, class _Pr, class _Pj>
static constexpr void _Sort_common(_It _First, _It _Last, iter_difference_t<_It> _Ideal, _Pr _Pred, _Pj _Proj) {
_STL_INTERNAL_STATIC_ASSERT(random_access_iterator<_It>);
_STL_INTERNAL_STATIC_ASSERT(sortable<_It, _Pr, _Pj>);
for (;;) {
if (_Last - _First <= _ISORT_MAX) {
_Insertion_sort_common(_STD move(_First), _STD move(_Last), _Pred, _Proj);
return;
}
if (_Ideal <= 0) {
_Make_heap_common(_First, _Last, _Pred, _Proj);
_Sort_heap_common(_STD move(_First), _STD move(_Last), _Pred, _Proj);
return;
}
auto [_Mid_first, _Mid_last] = _Partition_by_median_guess_common(_First, _Last, _Pred, _Proj);
_Ideal = (_Ideal >> 1) + (_Ideal >> 2);
if (_Mid_first - _First < _Last - _Mid_last) {
_Sort_common(_First, _STD move(_Mid_first), _Ideal, _Pred, _Proj);
_First = _STD move(_Mid_last);
} else {
_Sort_common(_STD move(_Mid_last), _Last, _Ideal, _Pred, _Proj);
_Last = _STD move(_Mid_first);
}
}
}
|
核心实现如上，代码块较长，请善用 shift + 滚轮
实现剖析
接下来我们来看一看具体的实现过程：
_Sort_common() 实际上可以划分为三个部分，先进行两次 if 判断，并确定到底是使用插入排序还是堆排序，当上述两者都不成立的时候就进入快速排序的部分。随后就是检验递归深度，决定下一次递归的排序方式。
1.插入排序
在循环体中的第一个 if 语句中， _ISORT_MAX 是一个宏定义，具体指定的值其实是32。
1
2
|
_INLINE_VAR constexpr int _ISORT_MAX = 32;
|
具体的实现就是常规的插入排序，具体可以查看 _Insertion_sort_common() 的函数定义，这里并不展开。
2.堆排序
在循环体中的第二个 if 语句中， _Ideal 是根据上一次递归范围来决定的。
1
2
3
4
5
6
7
8
9
10
11
|
_Ideal = (_Ideal >> 1) + (_Ideal >> 2);
if (_Mid_first - _First < _Last - _Mid_last) {
_Sort_common(_First, _STD move(_Mid_first), _Ideal, _Pred, _Proj);
_First = _STD move(_Mid_last);
} else {
_Sort_common(_STD move(_Mid_last), _Last, _Ideal, _Pred, _Proj);
_Last = _STD move(_Mid_first);
}
|
_Ideal 会在每次递归时进行一个对数级的递减，当这个值满足 if (_Ideal <= 0) 的时候，我们就认为递归过深，需要进行堆排序，进而执行 _Make_heap_common() 和 _Sort_heap_common() 。
事实上这里仅仅使用移位进行了简化计算，程序的原意是以 $1.5\log{n}$ 进行对数级递减。然而这里只是作为深度统计，并不需要这么精细的计算，移位最终结果应该也只是会到达 0 而不会是负数。
3.快速排序
最后就是进行快速排序，这里使用结构化绑定，将排序后的下一轮的要用到的递归结果传递出来。
1
2
|
auto [_Mid_first, _Mid_last] = _Partition_by_median_guess_common(_First, _Last, _Pred, _Proj);
|
具体的实现就是常规的快速排序，具体可以查看 _Partition_by_median_guess_common() 的函数定义，这里并不展开。
不过中间比较有意思的一点是，MSVC在实现中位数选择时采用了一个相当实用的办法。
具体的实现代码贴在了下面：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| template <random_access_iterator _It, class _Pr, class _Pj>
requires sortable<_It, _Pr, _Pj>
constexpr void _Guess_median_common(_It _First, _It _Mid, _It _Last, _Pr _Pred, _Pj _Proj) {
using _Diff = iter_difference_t<_It>;
const _Diff _Count = _Last - _First;
if (_Count > 40) {
const _Diff _Step = (_Count + 1) >> 3;
const _Diff _Two_step = _Step << 1;
_Med3_common(_First, _First + _Step, _First + _Two_step, _Pred, _Proj);
_Med3_common(_Mid - _Step, _Mid, _Mid + _Step, _Pred, _Proj);
_Med3_common(_Last - _Two_step, _Last - _Step, _Last, _Pred, _Proj);
_Med3_common(_First + _Step, _Mid, _Last - _Step, _Pred, _Proj);
} else {
_Med3_common(_First, _Mid, _Last, _Pred, _Proj);
}
}
|
tips: 其中的 _Med3_common() 就是在输入的三个元素中选取中位数
其中最主要的部分在于，当排序范围大于 40 时，使用了一种名为 Tukey's ninther 的算法。其实这个算法并不神秘，它真正要做的事就是将整个范围分成三段，三段在相同的位置各取三个元素，选出各段代表的中位数，最后将三个代表中位数再取一次中位，得到最终结果。
简单但又不失效率，所以说它是相当实用的算法。而且在实践当中证明，这样的做法至少比随机抽选中位数要好得多。
总结
STL中的算法和容器都被精心设计以达到高效性要求，尤其是时间和空间的复杂度控制，因此STL设计了很多优化策略。
但不要因此就认为STL就是神秘且复杂的，比如这里剖析的 ranges::sort 的实现就并非不可理解，其中甚至还出现了一些依赖实践和经验的设计方法。
例如 Tukey's ninther 就是在笔者读到 if (_Count > 40) 时才知道原来STL也会采用固定数值这样简单粗暴的办法来进行决策，也算是相当有趣了。
所以还是要多读源码，多看实现。总结就到这里，愿大家共勉。
