浅析 MSVC STL 中的 sort 实现

自从八月打完电赛，就忙着找工作和考研，好久没更新博客了。

前一阵子在刷算法题的时候，忽然开始好奇STL中的排序算法是如何实现的。
于是就去研究了 MSVC STL 中的 ranges::sort 的实现。

源代码请看这里 MSVC STL

内省排序

首先需要明确的是，C++标准并未严格规定 sort() 的具体实现。于是主流编译器 MSVC 和 GCC 中都选择了 内省排序(Introsort) 作为其具体的实现方式。

所谓内省排序，是一种混合算法。主要采用快速排序和堆排序共同完成排序功能。

众所周知的是，这两种排序各有优缺点。例如快速排序并不稳定，时间复杂度最优是 $O(n\log{n})$ ，而最差为 $O(n_2)$ 。虽然堆排序能够稳定实现 $O(n\log{n})$ ，但是在操作效率上不如快速排序（例如快速排序有较高的缓存使用率）。

但如果将两种算法混合使用，先用快速排序尝试进行几轮的排序，若递归深度过深，就转而采用堆排序，从而规避两种排序的缺点，并结合两者的优点，进而达到最好的效率。

在 MSVC 所选用的实现中，就采用了这样的思路。不过进行了少许的改进，在排序范围较小的时候直接采用插入排序，进一步加快排序速度。

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) {
    // sort [_First, _Last) with respect to _Pred and _Proj
    _STL_INTERNAL_STATIC_ASSERT(random_access_iterator<_It>);
    _STL_INTERNAL_STATIC_ASSERT(sortable<_It, _Pr, _Pj>);

    for (;;) {
        if (_Last - _First <= _ISORT_MAX) { // small
            _Insertion_sort_common(_STD move(_First), _STD move(_Last), _Pred, _Proj);
            return;
        }

        if (_Ideal <= 0) { // heap sort if too many divisions
            _Make_heap_common(_First, _Last, _Pred, _Proj);
            _Sort_heap_common(_STD move(_First), _STD move(_Last), _Pred, _Proj);
            return;
        }

        // divide and conquer by quicksort
        auto [_Mid_first, _Mid_last] = _Partition_by_median_guess_common(_First, _Last, _Pred, _Proj);

        _Ideal = (_Ideal >> 1) + (_Ideal >> 2); // allow 1.5 log2(N) divisions

        if (_Mid_first - _First < _Last - _Mid_last) { // loop on second half
            _Sort_common(_First, _STD move(_Mid_first), _Ideal, _Pred, _Proj);
            _First = _STD move(_Mid_last);
        } else { // loop on first half
            _Sort_common(_STD move(_Mid_last), _Last, _Ideal, _Pred, _Proj);
            _Last = _STD move(_Mid_first);
        }
    }
}

核心实现如上，代码块较长，请善用 shift + 滚轮

实现剖析

接下来我们来看一看具体的实现过程：

_Sort_common() 实际上可以划分为三个部分，先进行两次 if 判断，并确定到底是使用插入排序还是堆排序，当上述两者都不成立的时候就进入快速排序的部分。随后就是检验递归深度，决定下一次递归的排序方式。

1.插入排序

在循环体中的第一个 if 语句中， _ISORT_MAX 是一个宏定义，具体指定的值其实是32。

// maximum size for insertion sort
_INLINE_VAR constexpr int _ISORT_MAX = 32;

具体的实现就是常规的插入排序，具体可以查看 _Insertion_sort_common() 的函数定义，这里并不展开。

2.堆排序

在循环体中的第二个 if 语句中， _Ideal 是根据上一次递归范围来决定的。

// this is part of sort::_Sort_common()

_Ideal = (_Ideal >> 1) + (_Ideal >> 2); // allow 1.5 log2(N) divisions

if (_Mid_first - _First < _Last - _Mid_last) { // loop on second half
    _Sort_common(_First, _STD move(_Mid_first), _Ideal, _Pred, _Proj);
    _First = _STD move(_Mid_last);
} else { // loop on first half
    _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.快速排序

最后就是进行快速排序，这里使用结构化绑定，将排序后的下一轮的要用到的递归结果传递出来。

// divide and conquer by quicksort
auto [_Mid_first, _Mid_last] = _Partition_by_median_guess_common(_First, _Last, _Pred, _Proj);

具体的实现就是常规的快速排序，具体可以查看 _Partition_by_median_guess_common() 的函数定义，这里并不展开。

不过中间比较有意思的一点是，MSVC在实现中位数选择时采用了一个相当实用的办法。
具体的实现代码贴在了下面：

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) {
    // sort median element to middle
    using _Diff        = iter_difference_t<_It>;
    const _Diff _Count = _Last - _First;
    if (_Count > 40) { // Tukey's ninther
        const _Diff _Step     = (_Count + 1) >> 3; // +1 can't overflow because range was made inclusive in caller
        const _Diff _Two_step = _Step << 1; // note: intentionally discards low-order bit
        _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 的算法。其实这个算法并不神秘，它真正要做的事就是将整个范围分成三段，三段在相同的位置各取三个元素，选出各段代表的中位数，最后将三个代表中位数再取一次中位，得到最终结果。

简单但又不失效率，所以说它是相当实用的算法。而且在实践当中证明，这样的做法至少比随机抽选中位数要好得多。