很多人第一次打开 MSVC 的algorithm都是冲着std::sort去的。结果按 F12 跳进实现迎面就是_Sort_unchecked、_Insertion_sort_unchecked、_Partition_by_median_guess_unchecked这么一串带下划线的内部函数很多人直接就退了。这篇文章就是来拆掉这堵墙std::sort的本质是三套算法在接力——快排当主力插入排序收拾小尾巴堆排序负责兜底。整条链路走一遍你会发现真正核心的排序代码其实不到一百行。下面以微软开源仓库里那版实现为主线和你本地 VS 安装目录下的include/algorithm基本一致。读完你至少能回答这几个问题为什么std::sort不是纯快排32 这个阈值是哪来的那行(_Ideal 1) (_Ideal 2)到底在干嘛以及有哪些坑是源码里一眼就能看穿的。先给你一个十秒版结论std::sort的完整逻辑是——区间长度小于等于 32 就用插入排序否则快排分区每分区一次预算乘 3/4预算耗尽就整段切堆排序。剩下的全是细节。1. 入口只是皮sort() 到 _Sort_unchecked 的管线1.1 公开重载内部做了什么std::sort有两个重载一个不带比较器一个带比较器。不带的那版内部用less也就是operator。无论哪个重载最后都会钻进同一个内部函数。在 MSVC 里公开入口的写法大致是这样template class _RanIt, class _Pr void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last) _Adl_verify_range(_First, _Last); const auto _UFirst _Get_unwrapped(_First); const auto _ULast _Get_unwrapped(_Last); _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pred); }这里的_Adl_verify_range负责在调试构建下做范围合法性检查用的是 ADL 派发能兼容各种自定义容器。_Get_unwrapped则是把迭代器拆包装。为什么要拆因为 MSVC 在 debug 构建里给迭代器套了一层壳里面有指针、有容器信息、有各种调试元数据_Get_unwrapped能把壳剥掉露出底层指针。这个动作非常关键——_Sort_unchecked内部是高频递归如果每一层都再做一次边界校验性能就全毁了。所以设计策略是公开入口校验一次内部函数拿到裸指针后默认你懂规矩。带_unchecked后缀的函数全是这条路。注意第三个参数_ULast - _UFirst表面看是元素个数 N但到了_Sort_unchecked里它摇身一变成了递归预算_Ideal。这个预算怎么花是理解整个算法策略的钥匙。1.2 _Sort_unchecked 的三分支循环骨架内部最核心的函数就是排序真正的大本营_Sort_uncheckedtemplate class _RanIt, class _Pr void _Sort_unchecked(_RanIt _First, _RanIt _Last, _Iter_diff_t_RanIt _Ideal, _Pr _Pred) { // order [_First, _Last) for (;;) { if (_Last - _First _ISORT_MAX) { // 区间很小插入排序 _Insertion_sort_unchecked(_First, _Last, _Pred); return; } if (_Ideal 0) { // 快排预算耗尽堆排序 _Make_heap_unchecked(_First, _Last, _Pred); _Sort_heap_unchecked(_First, _Last, _Pred); return; } // 主路径快排分区 auto _Mid _Partition_by_median_guess_unchecked(_First, _Last, _Pred); // 预算按 3/4 衰减 _Ideal (_Ideal 1) (_Ideal 2); // 只递归较小的一半较大的一半交给循环 if (_Mid.first - _First _Last - _Mid.second) { _Sort_unchecked(_First, _Mid.first, _Ideal, _Pred); _First _Mid.second; } else { _Sort_unchecked(_Mid.second, _Last, _Ideal, _Pred); _Last _Mid.first; } } }先解释for (;;)这种写法。快排天然是递归的但这里写成循环 递归半边每次分区后比较左右两段哪边更短递归调用短的那一半长的那一半不递归而是挪动_First或_Last后继续循环。这就把每次递归只保留较短子问题做到了极致调用栈深度被限制在 O(log N) 量级。哪怕完全没有堆排序兜底单靠这一招快排因为递归路径失控导致的栈溢出问题就被挡掉了大半。这是读这份源码时最容易忽略、但含金量最高的工程细节。_ISORT_MAX是头文件里的常量值就是 32。区间长度小于等于 32直接结束快排改用插入排序收尾。_Ideal初始等于 N每做一次分区就乘 3/4一旦小于等于 0说明快排折腾了很多轮还没搞定继续赌主元质量可能被恶意输入带进沟里于是整体切堆排序。看到这里std::sort的全局结构已经结束了。快排是主干为什么叫median_guess、怎么分区是下一件要看的事。2. 主力快排median-of-three 选主元和分区的关键细节2.1 为什么是猜中位数而不是随机或取首元素任何快排的品质都由主元决定。取_First当主元遇到已经排好序的数组每一轮只能削掉一个元素退化成 O(N²)。随机主元能抗攻击但生成随机数有成本还引入全局状态在追求确定性和可复现行为的库代码里这不是首选。取首、中、尾三个位置的中位数当主元成本只是三次比较加几次交换换来的是对已排序逆序重复前缀这些最常见病态输入的天然抵抗。这三个位置的中间值在数组基本有序时几乎就是真正的中位数分区会非常均衡。_Partition_by_median_guess_unchecked开头干的事就是让这三个样本先有序_RanIt _Mid _First ((_Last - _First) 1); // 取中间位置 if (_Pred(*_Mid, *_First)) { _STD iter_swap(_Mid, _First); // 让 *_First 成为三者最小 } if (_Pred(*(_Last - 1), *_Mid)) { _STD iter_swap(_Last - 1, _Mid); // 让 *_Mid 成为三者中间 } if (_Pred(*_Mid, *_First)) { _STD iter_swap(_Mid, _First); }走完这三个 if必然有*_First *_Mid *(_Last - 1)主元就是*_Mid。这段代码也是排序三个元素的标准姿势你写插入排序、写一堆 swap最后都会被编译器优化成这种链式 if 交换。以后想手动实现三元素排序直接抄这个结构就行。2.2 双指针扫描与返回值的语义选定主元后分区用两个指针从_First 1和_Last - 2往中间走左边找大于等于主元的右边找小于等于主元的找到就交换直到两个指针相遇。这里藏着一个细节因为三个样本已经有序*_First必然小于等于主元*(_Last - 1)必然大于等于主元左右两侧都等于提前放好了哨兵。扫描循环里可以省掉一部分越界判断不用担心指针飞出区间。这是 median-of-three 带来的隐藏红利不读源码很难发现。函数返回的不是单个迭代器而是一个 pairpair_RanIt, _RanIt _Partition_by_median_guess_unchecked(...);返回的两个迭代器_Mid.first、_Mid.second划出一段中间已就位的区间。_Sort_unchecked里只递归[_First, _Mid.first)和[_Mid.second, _Last)中间这段——至少包含主元如果碰到大量重复元素还可能包含一批与主元相等的值——不再参与后续排序。这其实就是三分区思想的影子把等于主元的元素留在中间两边递归时不会被重复触碰。对重复元素极多的输入这个设计能显著减少无用比较。不同小版本里 Partition 内部细节会略有差异比如相等元素怎么换、主元最后从哪边放回去但三个样本有序 双指针扫描 pair 返回中间区间这个大框架是不变的。顺便回答一个高频面试问题的一半std::sort为什么不稳定因为主元会被从_Mid挪来挪去median-of-three 的交换也可能跨越其他相等元素相等键值的相对顺序在分区过程中就被打乱了。源码已经把答案写在这里了。3. 小数组的胜负手插入排序的阈值与快速路径3.1 为什么 32 这个数字值得信任递归不断下探区间最终会变得很小。当区间已经小于等于 32 时继续做快排分区是亏的选主元、双指针扫描、交换主元这些固定开销在小数组上可能比一个 O(N²) 的简单排序还贵。插入排序虽然比较次数最坏是 O(N²)但常数极小对基本有序的数据它几乎退化成线性行为。它只做相邻移动cache 局部性极好。32 这个数不是算出来的是长期 Benchmark 测出来的经验交叉点——小于这个规模平方级排序的简单性赢了大于这个规模快排的 O(N log N) 优势开始体现。说个参照GCC 的 libstdc 里这个阈值是 16MSVC 选了 32。两个数字都没有标准答案都是各家的实测调优结果。以后看到为什么这里用 32这类问题回答经验值 实测调优比背数字更靠谱。3.2 插入排序源码里的两条路径_Insertion_sort_unchecked的主干思想是维护一个[_First, _Next)有序前缀每次把*_Next插到合适位置。但 MSVC 的实现里藏了一个非常实用的小优化看代码template class _RanIt, class _Pr void _Insertion_sort_unchecked(_RanIt _First, _RanIt _Last, _Pr _Pred) { if (_First ! _Last) { for (_RanIt _Next _First; _Next ! _Last; ) { _RanIt _Prev _Next; if (_DEBUG_LT_PRED(_Pred, *_Next, *_First)) { // 新元素比整个前缀都小 _Iter_value_t_RanIt _Val _STD move(*_Next); _Move_backward_unchecked(_First, _Prev, _Prev 1); // 前缀整体右移 *_First _STD move(_Val); } else { // 普通插入 _RanIt _Cur _Prev; for (; _DEBUG_LT_PRED(_Pred, *_Cur, *_--_Prev); _Cur _Prev) { *_Cur _STD move(*_Prev); // 把空洞往前挪 } *_Cur _STD move(*_Next); // 新元素填进空洞 } } } }先看普通路径。_Prev从_Next开始往前退_Cur记录空洞位置。每次发现前一个元素比*_Next大就把那个元素右移到空洞里空洞自己往前走一步直到前面的元素不再大于*_Next把*_Next写进空洞。全程只用 move不产生拷贝每个元素最多被写一次。这比教科书里那种反复 swap 的版本少了将近一半的写操作cache 友好得多。再看快速路径如果*_Next比有序前缀的第一个元素还小那它直接就是新的全局最小。这种情况没必要从右往左逐个比较直接把新元素取出来用_Move_backward_unchecked把整个前缀右移一格再把它写回头部。这个优化对数据接近有序但偶尔冒出一个极小数的场景帮助很大把最坏的一轮插入从 O(K) 次比较压缩成一次区间搬运。_DEBUG_LT_PRED这个宏也值得单独说。release 下它就是直接调用_Pred(a, b)debug 下会附带额外的检查是 MSVC 给比较器加的安全阀。我遇到过有人把a b写成a b的排序代码release 模式跑起来飞快但结果乱序开 debug 一跑问题当场现形。写排序比较器时严格弱序这四字真言不是说着玩的。4. 兜底堆排_Ideal 衰减如何锁死最坏情况4.1 3/4 衰减和它的边界再回到_Ideal这行_Ideal (_Ideal 1) (_Ideal 2);它等价于_Ideal _Ideal * 3 / 4只是用移位实现而已。初始_Ideal N每一轮快排分区后都乘一次 3/4。等它衰减到 0说明快排干了很多活但还没把区间收拾利索按源码注释的说法这相当于给了大约 1.5 log2(N) 轮分区的冗余。超过预算就不再赌主元质量了直接换成确定性算法收场。为什么是 3/4 而不是 1/2因为分区均衡时子问题规模是指数缩小的预算按 1/2 衰减会太紧主元稍微差一点就误伤3/4 给了更多冗余又不会无限放任。整数右移也保证了一定会衰减到 0不会出现下溢死循环。这个衰减预算模式比直接写死递归深度超过 log2(N) 就切堆排更平滑因为它同时兼容了不同分区质量的场景。4.2 堆排序的两个组成部分_Make_heap_unchecked和_Sort_heap_unchecked对应的就是公开接口std::make_heap和std::sort_heap。堆排序在这里当兜底因为它是标准库公认的稳定最坏复杂度选项最坏情况 O(N log N) 次比较只需要 O(1) 辅助空间。_Make_heap_unchecked采用自底向上建堆复杂度是 O(N)_Sort_heap_unchecked反复把堆顶元素和当前末尾交换再对缩小的堆做下沉调整复杂度是 O(N log N)。实现里还有一个比较器反转的小技巧——直接把_Pred反着用让同一个谓词既能控制建堆方向又能控制排序方向省掉一个greater的模板实例。4.3 为什么宁可快排先上也不直接堆排堆排序的常数太大了。下沉过程每次访问的地址都是1, 2, 4, 8...这种跳跃间隔cache 局部性比快排的线性扫描差得多交换次数也比快排高。同一份数据堆排序的实际耗时往往比快排慢 2 到 4 倍。所以 introsort 的设计哲学很务实快排是高期望值的赌徒只要主元质量在线它大概率赢得很漂亮堆排序是稳健的保守派专门负责在赌徒输光时保住下限。_Ideal就是那个止损点。这个设计还有一个容易被忽略的收益排序过程中递归深度被只递归小半边和_Ideal双重限制所以哪怕输入是专门针对 median-of-three 弱点构造的序列std::sort也不会栈溢出。这个保证是绝大多数手写快排做不到的。4.4 切堆排之后实际会发生什么如果你刻意构造一个能骗过 median-of-three 的序列会看到 sort 在中途切换成堆排序。此时整体复杂度依然是 O(N log N)但实际耗时明显变长。日常业务里很少遇到这种输入但知道这个机制后你就能解释一个现象某些几乎有序但带着周期性抖动的大数组排序反而比随机数组慢。不是算法开小差而是它检测到分区持续不均衡主动切到了更稳但更慢的路线。顺带一提MSVC 的并行std::sort走的是另一条路把区间切块每块独立走这套核心排序最后再归并。串行版本的这套 introsort 机制在并行版本里依然是每个分块的基础。5. 读完源码之后值得带走的几件事5.1 std::sort 不是稳定的——源码已经写得很明白分区时主元会被从_Mid挪走median-of-three 还会交换三个样本任何一步都可能改变相同键值元素的相对顺序。需要保持相对顺序就用std::stable_sort它内部是归并排序最坏 O(N log N)但可能要额外分配缓冲区。代价很实在内存和时间都更贵。5.2 迭代器要求为什么 list 上写 std::sort 编译不过_Sort_unchecked里到处是_Last - _First、_First ((_Last - _First) 1)这类随机访问运算。链表的迭代器没有operator-和operator模板实例化时直接编译失败。这不是 MSVC 抠门是算法本身要求随机访问。遇到std::list和std::forward_list用它们自己的sort()成员函数就好那是归并排序专为链式结构设计。5.3 调试构建是对付坏比较器的第一道防线_DEBUG_LT_PRED在 debug 下会做额外检查。最典型的翻车现场是结构体数组比较器只比较其中一个字段而那个字段有重复release 跑出来好像没问题debug 一跑立刻报警。我的建议是开发期保留默认的迭代器调试级别把排序相关的诡异 bug 交给断言去抓上线构建再关掉换取速度。排序问题里八成是严格弱序被打破debug 模式能帮你省下一个下午。5.4 三个主流库实现其实是同一个思路实现小数组策略阈值递归上限控制MSVC插入排序32_Ideal按 3/4 衰减耗尽转堆排libstdcGCC插入排序162 * log2(N)深度限制libcLLVM插入排序更小深度限制策略超限转堆排libstdc 的std::sort同样是 introsort插入排序收小数组递归深度超限切堆排只是函数名从_Sort_unchecked变成了__introsort_loop。libc 也是快排 插入排序 堆排的组合。中位三取、小数组插入排序、深度超限堆排这三个特征三大库互相印证说明这套设计经得起工业级检验。C20 的ranges::sort在 MSVC 里也复用同一套核心。5.5 从源码里得出的选型建议只要前 K 个有序结果别用sort用partial_sort它只维护一个 K 大小的堆省掉大量无用全排序。只要第 K 大的值用nth_element它就是快排分区的直接产品期望 O(N)。要稳定排序用stable_sort别自己写带序号的手动稳定。数据基本有序但体量很大也别急着手动优化std::sort的插入排序尾巴对近有序输入表现很好。想在多核机器上提速可以直接给 sort 加执行策略参数MSVC 的并行版本会分块走同一套核心。我自己现在的习惯是凡是排序先写std::sort测出问题再看是稳定性、比较器还是内存布局的问题很少再手写快排。看完实现之后你就明白为什么行业里总说别自己造排序轮子——不是快排打不过堆排而是 STL 把三套算法、预算限制、哨兵优化、move 语义全部焊在一起了。最后分享一个读源码的小技巧。在 VS 里对std::sort按 F12会先跳到公共重载然后一步一步走进_Sort_unchecked。这时候别急着往更深处钻先看函数签名和顶部注释分清这个函数负责哪一层、调用谁、被谁调用再读循环体。带下划线的函数看着吓人其实命名规律很规则_unchecked表示不做范围检查_Pred表示比较器参数_First/_Last表示区间。记住这几个前缀整个algorithm的门槛就塌了一半。我最初翻这份源码是想验证手写快排到底能不能打赢 std::sort。结论当然是不能——不是因为快排的思路不行而是 STL 把工程层面的细节全补齐了。了解这些之后我不光会用std::sort还能在项目里解释它为什么快、什么时候会慢、什么时候该换别的排序。希望你读完也有同样的感觉。 
长河君 · 2026/10/21 22:07:01 · 阅读 1.2k MSVC std::sort 底层实现：快排、插入排序与堆排序的三重奏
很多人第一次打开 MSVC 的algorithm都是冲着std::sort去的。结果按 F12 跳进实现迎面就是_Sort_unchecked、_Insertion_sort_unchecked、_Partition_by_median_guess_unchecked这么一串带下划线的内部函数很多人直接就退了。这篇文章就是来拆掉这堵墙std::sort的本质是三套算法在接力——快排当主力插入排序收拾小尾巴堆排序负责兜底。整条链路走一遍你会发现真正核心的排序代码其实不到一百行。下面以微软开源仓库里那版实现为主线和你本地 VS 安装目录下的include/algorithm基本一致。读完你至少能回答这几个问题为什么std::sort不是纯快排32 这个阈值是哪来的那行(_Ideal 1) (_Ideal 2)到底在干嘛以及有哪些坑是源码里一眼就能看穿的。先给你一个十秒版结论std::sort的完整逻辑是——区间长度小于等于 32 就用插入排序否则快排分区每分区一次预算乘 3/4预算耗尽就整段切堆排序。剩下的全是细节。1. 入口只是皮sort() 到 _Sort_unchecked 的管线1.1 公开重载内部做了什么std::sort有两个重载一个不带比较器一个带比较器。不带的那版内部用less也就是operator。无论哪个重载最后都会钻进同一个内部函数。在 MSVC 里公开入口的写法大致是这样template class _RanIt, class _Pr void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last) _Adl_verify_range(_First, _Last); const auto _UFirst _Get_unwrapped(_First); const auto _ULast _Get_unwrapped(_Last); _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pred); }这里的_Adl_verify_range负责在调试构建下做范围合法性检查用的是 ADL 派发能兼容各种自定义容器。_Get_unwrapped则是把迭代器拆包装。为什么要拆因为 MSVC 在 debug 构建里给迭代器套了一层壳里面有指针、有容器信息、有各种调试元数据_Get_unwrapped能把壳剥掉露出底层指针。这个动作非常关键——_Sort_unchecked内部是高频递归如果每一层都再做一次边界校验性能就全毁了。所以设计策略是公开入口校验一次内部函数拿到裸指针后默认你懂规矩。带_unchecked后缀的函数全是这条路。注意第三个参数_ULast - _UFirst表面看是元素个数 N但到了_Sort_unchecked里它摇身一变成了递归预算_Ideal。这个预算怎么花是理解整个算法策略的钥匙。1.2 _Sort_unchecked 的三分支循环骨架内部最核心的函数就是排序真正的大本营_Sort_uncheckedtemplate class _RanIt, class _Pr void _Sort_unchecked(_RanIt _First, _RanIt _Last, _Iter_diff_t_RanIt _Ideal, _Pr _Pred) { // order [_First, _Last) for (;;) { if (_Last - _First _ISORT_MAX) { // 区间很小插入排序 _Insertion_sort_unchecked(_First, _Last, _Pred); return; } if (_Ideal 0) { // 快排预算耗尽堆排序 _Make_heap_unchecked(_First, _Last, _Pred); _Sort_heap_unchecked(_First, _Last, _Pred); return; } // 主路径快排分区 auto _Mid _Partition_by_median_guess_unchecked(_First, _Last, _Pred); // 预算按 3/4 衰减 _Ideal (_Ideal 1) (_Ideal 2); // 只递归较小的一半较大的一半交给循环 if (_Mid.first - _First _Last - _Mid.second) { _Sort_unchecked(_First, _Mid.first, _Ideal, _Pred); _First _Mid.second; } else { _Sort_unchecked(_Mid.second, _Last, _Ideal, _Pred); _Last _Mid.first; } } }先解释for (;;)这种写法。快排天然是递归的但这里写成循环 递归半边每次分区后比较左右两段哪边更短递归调用短的那一半长的那一半不递归而是挪动_First或_Last后继续循环。这就把每次递归只保留较短子问题做到了极致调用栈深度被限制在 O(log N) 量级。哪怕完全没有堆排序兜底单靠这一招快排因为递归路径失控导致的栈溢出问题就被挡掉了大半。这是读这份源码时最容易忽略、但含金量最高的工程细节。_ISORT_MAX是头文件里的常量值就是 32。区间长度小于等于 32直接结束快排改用插入排序收尾。_Ideal初始等于 N每做一次分区就乘 3/4一旦小于等于 0说明快排折腾了很多轮还没搞定继续赌主元质量可能被恶意输入带进沟里于是整体切堆排序。看到这里std::sort的全局结构已经结束了。快排是主干为什么叫median_guess、怎么分区是下一件要看的事。2. 主力快排median-of-three 选主元和分区的关键细节2.1 为什么是猜中位数而不是随机或取首元素任何快排的品质都由主元决定。取_First当主元遇到已经排好序的数组每一轮只能削掉一个元素退化成 O(N²)。随机主元能抗攻击但生成随机数有成本还引入全局状态在追求确定性和可复现行为的库代码里这不是首选。取首、中、尾三个位置的中位数当主元成本只是三次比较加几次交换换来的是对已排序逆序重复前缀这些最常见病态输入的天然抵抗。这三个位置的中间值在数组基本有序时几乎就是真正的中位数分区会非常均衡。_Partition_by_median_guess_unchecked开头干的事就是让这三个样本先有序_RanIt _Mid _First ((_Last - _First) 1); // 取中间位置 if (_Pred(*_Mid, *_First)) { _STD iter_swap(_Mid, _First); // 让 *_First 成为三者最小 } if (_Pred(*(_Last - 1), *_Mid)) { _STD iter_swap(_Last - 1, _Mid); // 让 *_Mid 成为三者中间 } if (_Pred(*_Mid, *_First)) { _STD iter_swap(_Mid, _First); }走完这三个 if必然有*_First *_Mid *(_Last - 1)主元就是*_Mid。这段代码也是排序三个元素的标准姿势你写插入排序、写一堆 swap最后都会被编译器优化成这种链式 if 交换。以后想手动实现三元素排序直接抄这个结构就行。2.2 双指针扫描与返回值的语义选定主元后分区用两个指针从_First 1和_Last - 2往中间走左边找大于等于主元的右边找小于等于主元的找到就交换直到两个指针相遇。这里藏着一个细节因为三个样本已经有序*_First必然小于等于主元*(_Last - 1)必然大于等于主元左右两侧都等于提前放好了哨兵。扫描循环里可以省掉一部分越界判断不用担心指针飞出区间。这是 median-of-three 带来的隐藏红利不读源码很难发现。函数返回的不是单个迭代器而是一个 pairpair_RanIt, _RanIt _Partition_by_median_guess_unchecked(...);返回的两个迭代器_Mid.first、_Mid.second划出一段中间已就位的区间。_Sort_unchecked里只递归[_First, _Mid.first)和[_Mid.second, _Last)中间这段——至少包含主元如果碰到大量重复元素还可能包含一批与主元相等的值——不再参与后续排序。这其实就是三分区思想的影子把等于主元的元素留在中间两边递归时不会被重复触碰。对重复元素极多的输入这个设计能显著减少无用比较。不同小版本里 Partition 内部细节会略有差异比如相等元素怎么换、主元最后从哪边放回去但三个样本有序 双指针扫描 pair 返回中间区间这个大框架是不变的。顺便回答一个高频面试问题的一半std::sort为什么不稳定因为主元会被从_Mid挪来挪去median-of-three 的交换也可能跨越其他相等元素相等键值的相对顺序在分区过程中就被打乱了。源码已经把答案写在这里了。3. 小数组的胜负手插入排序的阈值与快速路径3.1 为什么 32 这个数字值得信任递归不断下探区间最终会变得很小。当区间已经小于等于 32 时继续做快排分区是亏的选主元、双指针扫描、交换主元这些固定开销在小数组上可能比一个 O(N²) 的简单排序还贵。插入排序虽然比较次数最坏是 O(N²)但常数极小对基本有序的数据它几乎退化成线性行为。它只做相邻移动cache 局部性极好。32 这个数不是算出来的是长期 Benchmark 测出来的经验交叉点——小于这个规模平方级排序的简单性赢了大于这个规模快排的 O(N log N) 优势开始体现。说个参照GCC 的 libstdc 里这个阈值是 16MSVC 选了 32。两个数字都没有标准答案都是各家的实测调优结果。以后看到为什么这里用 32这类问题回答经验值 实测调优比背数字更靠谱。3.2 插入排序源码里的两条路径_Insertion_sort_unchecked的主干思想是维护一个[_First, _Next)有序前缀每次把*_Next插到合适位置。但 MSVC 的实现里藏了一个非常实用的小优化看代码template class _RanIt, class _Pr void _Insertion_sort_unchecked(_RanIt _First, _RanIt _Last, _Pr _Pred) { if (_First ! _Last) { for (_RanIt _Next _First; _Next ! _Last; ) { _RanIt _Prev _Next; if (_DEBUG_LT_PRED(_Pred, *_Next, *_First)) { // 新元素比整个前缀都小 _Iter_value_t_RanIt _Val _STD move(*_Next); _Move_backward_unchecked(_First, _Prev, _Prev 1); // 前缀整体右移 *_First _STD move(_Val); } else { // 普通插入 _RanIt _Cur _Prev; for (; _DEBUG_LT_PRED(_Pred, *_Cur, *_--_Prev); _Cur _Prev) { *_Cur _STD move(*_Prev); // 把空洞往前挪 } *_Cur _STD move(*_Next); // 新元素填进空洞 } } } }先看普通路径。_Prev从_Next开始往前退_Cur记录空洞位置。每次发现前一个元素比*_Next大就把那个元素右移到空洞里空洞自己往前走一步直到前面的元素不再大于*_Next把*_Next写进空洞。全程只用 move不产生拷贝每个元素最多被写一次。这比教科书里那种反复 swap 的版本少了将近一半的写操作cache 友好得多。再看快速路径如果*_Next比有序前缀的第一个元素还小那它直接就是新的全局最小。这种情况没必要从右往左逐个比较直接把新元素取出来用_Move_backward_unchecked把整个前缀右移一格再把它写回头部。这个优化对数据接近有序但偶尔冒出一个极小数的场景帮助很大把最坏的一轮插入从 O(K) 次比较压缩成一次区间搬运。_DEBUG_LT_PRED这个宏也值得单独说。release 下它就是直接调用_Pred(a, b)debug 下会附带额外的检查是 MSVC 给比较器加的安全阀。我遇到过有人把a b写成a b的排序代码release 模式跑起来飞快但结果乱序开 debug 一跑问题当场现形。写排序比较器时严格弱序这四字真言不是说着玩的。4. 兜底堆排_Ideal 衰减如何锁死最坏情况4.1 3/4 衰减和它的边界再回到_Ideal这行_Ideal (_Ideal 1) (_Ideal 2);它等价于_Ideal _Ideal * 3 / 4只是用移位实现而已。初始_Ideal N每一轮快排分区后都乘一次 3/4。等它衰减到 0说明快排干了很多活但还没把区间收拾利索按源码注释的说法这相当于给了大约 1.5 log2(N) 轮分区的冗余。超过预算就不再赌主元质量了直接换成确定性算法收场。为什么是 3/4 而不是 1/2因为分区均衡时子问题规模是指数缩小的预算按 1/2 衰减会太紧主元稍微差一点就误伤3/4 给了更多冗余又不会无限放任。整数右移也保证了一定会衰减到 0不会出现下溢死循环。这个衰减预算模式比直接写死递归深度超过 log2(N) 就切堆排更平滑因为它同时兼容了不同分区质量的场景。4.2 堆排序的两个组成部分_Make_heap_unchecked和_Sort_heap_unchecked对应的就是公开接口std::make_heap和std::sort_heap。堆排序在这里当兜底因为它是标准库公认的稳定最坏复杂度选项最坏情况 O(N log N) 次比较只需要 O(1) 辅助空间。_Make_heap_unchecked采用自底向上建堆复杂度是 O(N)_Sort_heap_unchecked反复把堆顶元素和当前末尾交换再对缩小的堆做下沉调整复杂度是 O(N log N)。实现里还有一个比较器反转的小技巧——直接把_Pred反着用让同一个谓词既能控制建堆方向又能控制排序方向省掉一个greater的模板实例。4.3 为什么宁可快排先上也不直接堆排堆排序的常数太大了。下沉过程每次访问的地址都是1, 2, 4, 8...这种跳跃间隔cache 局部性比快排的线性扫描差得多交换次数也比快排高。同一份数据堆排序的实际耗时往往比快排慢 2 到 4 倍。所以 introsort 的设计哲学很务实快排是高期望值的赌徒只要主元质量在线它大概率赢得很漂亮堆排序是稳健的保守派专门负责在赌徒输光时保住下限。_Ideal就是那个止损点。这个设计还有一个容易被忽略的收益排序过程中递归深度被只递归小半边和_Ideal双重限制所以哪怕输入是专门针对 median-of-three 弱点构造的序列std::sort也不会栈溢出。这个保证是绝大多数手写快排做不到的。4.4 切堆排之后实际会发生什么如果你刻意构造一个能骗过 median-of-three 的序列会看到 sort 在中途切换成堆排序。此时整体复杂度依然是 O(N log N)但实际耗时明显变长。日常业务里很少遇到这种输入但知道这个机制后你就能解释一个现象某些几乎有序但带着周期性抖动的大数组排序反而比随机数组慢。不是算法开小差而是它检测到分区持续不均衡主动切到了更稳但更慢的路线。顺带一提MSVC 的并行std::sort走的是另一条路把区间切块每块独立走这套核心排序最后再归并。串行版本的这套 introsort 机制在并行版本里依然是每个分块的基础。5. 读完源码之后值得带走的几件事5.1 std::sort 不是稳定的——源码已经写得很明白分区时主元会被从_Mid挪走median-of-three 还会交换三个样本任何一步都可能改变相同键值元素的相对顺序。需要保持相对顺序就用std::stable_sort它内部是归并排序最坏 O(N log N)但可能要额外分配缓冲区。代价很实在内存和时间都更贵。5.2 迭代器要求为什么 list 上写 std::sort 编译不过_Sort_unchecked里到处是_Last - _First、_First ((_Last - _First) 1)这类随机访问运算。链表的迭代器没有operator-和operator模板实例化时直接编译失败。这不是 MSVC 抠门是算法本身要求随机访问。遇到std::list和std::forward_list用它们自己的sort()成员函数就好那是归并排序专为链式结构设计。5.3 调试构建是对付坏比较器的第一道防线_DEBUG_LT_PRED在 debug 下会做额外检查。最典型的翻车现场是结构体数组比较器只比较其中一个字段而那个字段有重复release 跑出来好像没问题debug 一跑立刻报警。我的建议是开发期保留默认的迭代器调试级别把排序相关的诡异 bug 交给断言去抓上线构建再关掉换取速度。排序问题里八成是严格弱序被打破debug 模式能帮你省下一个下午。5.4 三个主流库实现其实是同一个思路实现小数组策略阈值递归上限控制MSVC插入排序32_Ideal按 3/4 衰减耗尽转堆排libstdcGCC插入排序162 * log2(N)深度限制libcLLVM插入排序更小深度限制策略超限转堆排libstdc 的std::sort同样是 introsort插入排序收小数组递归深度超限切堆排只是函数名从_Sort_unchecked变成了__introsort_loop。libc 也是快排 插入排序 堆排的组合。中位三取、小数组插入排序、深度超限堆排这三个特征三大库互相印证说明这套设计经得起工业级检验。C20 的ranges::sort在 MSVC 里也复用同一套核心。5.5 从源码里得出的选型建议只要前 K 个有序结果别用sort用partial_sort它只维护一个 K 大小的堆省掉大量无用全排序。只要第 K 大的值用nth_element它就是快排分区的直接产品期望 O(N)。要稳定排序用stable_sort别自己写带序号的手动稳定。数据基本有序但体量很大也别急着手动优化std::sort的插入排序尾巴对近有序输入表现很好。想在多核机器上提速可以直接给 sort 加执行策略参数MSVC 的并行版本会分块走同一套核心。我自己现在的习惯是凡是排序先写std::sort测出问题再看是稳定性、比较器还是内存布局的问题很少再手写快排。看完实现之后你就明白为什么行业里总说别自己造排序轮子——不是快排打不过堆排而是 STL 把三套算法、预算限制、哨兵优化、move 语义全部焊在一起了。最后分享一个读源码的小技巧。在 VS 里对std::sort按 F12会先跳到公共重载然后一步一步走进_Sort_unchecked。这时候别急着往更深处钻先看函数签名和顶部注释分清这个函数负责哪一层、调用谁、被谁调用再读循环体。带下划线的函数看着吓人其实命名规律很规则_unchecked表示不做范围检查_Pred表示比较器参数_First/_Last表示区间。记住这几个前缀整个algorithm的门槛就塌了一半。我最初翻这份源码是想验证手写快排到底能不能打赢 std::sort。结论当然是不能——不是因为快排的思路不行而是 STL 把工程层面的细节全补齐了。了解这些之后我不光会用std::sort还能在项目里解释它为什么快、什么时候会慢、什么时候该换别的排序。希望你读完也有同样的感觉。