比 std::sort 更快的快速排序：无分支分区、排序网络与稳健枢轴
来源：tiki.li — 2026-11-05
📋 概述
作者发布了 blqsort，一个单头文件的 C++/C 快速排序，声称在随机数据上没有已知的通用比较排序能更快，只有针对原始小类型的 SIMD 专门算法例外。三个支点：无分支分区、小分区用排序网络、更稳健的枢轴选择。基准是排序 5000 万个随机 double：M1 上 std::sort 1.33 s、ClickHouse 的 ipnsort 移植版 0.99 s、blqsort 0.67 s；Intel i5-9300H 上分别是 4.97 s、2.31 s、1.33 s。排序 5000 万个结构体时差距更大，M1 上 3.45 s 对 0.75 s。
🔑 核心要点
- 分区循环被改成无分支：先无条件写入，再把比较结果当增量加进游标（lwr += h; rwr -= !h），避开不可预测的分支预测失败。
- 无分支之所以快有实测：把小于 500 的数挑进新数组，if 版 0.345 s、无分支版 0.036 s，相差近十倍；汇编里前者是 b.gt，后者是 cinc。
- 小分区（≤16）走手工排序网络，每个尺寸一个分支、用 for (int i = 16; i--;) 让编译器展开 16 份，比插入排序更快。
- 枢轴用多个中位数的中位数再注入随机性，分布仍不均时退回堆排序，并把大量相同元素识别成一组。
- 已排序与逆序输入会被检测并高效处理；M1 上多线程版还能再快约 3 倍。
💡 金句
我不知道还有哪个通用的、基于比较的排序算法在随机数据上比它更快。
👍 0
👎 0
← 返回 Lobsters 首页