排序基准测试：用数据说话

“不要猜，去测。” ——每一个严肃的性能工程师

排序是计算机科学里最经典的问题之一，但“哪种排序最快”从来没有一个脱离上下文的答案。数据规模、数据分布、元素类型、缓存行为、标准库实现、编译器版本，都会影响最后结果。

本文只做一件事：把仓库里的排序 benchmark 变成可以直接执行、可以重新出 CSV、可以重新画图的版本，然后在当前环境下重跑一次，用真实结果回答“什么时候该用什么排序”。

先说结论：这篇文章的旧版本并不是当前仓库里可直接复现的实测稿。 当时仓库只有文章中的代码片段和手工绘制的 SVG，没有独立的 benchmark 源码、没有原始 CSV，也没有一条能直接执行的构建命令。所以旧稿里的具体数字，不能算当前仓库内可验证的真实数据。

这次我把可执行代码补到了 examples/sort-bench/，并在当前环境重跑了一遍：x86-64 Linux，12th Gen Intel Core i9-12900K，GCC 15.2.1，单线程 taskset -c 4 绑核。文中的表格和图都来自这次重新生成的 CSV。

代码与原始结果：bench.cpp | Makefile | README.md | results-current-env.csv | plot.py

一、基准测试方法论

1.1 micro-benchmark 的几个基本陷阱

陷阱一：编译器把你的工作优化掉了

如果排序结果没有被观测到，编译器可能直接把整个调用删掉。常见做法是加汇编栅栏：

inline void do_not_optimize(const void* ptr) {
    asm volatile("" : : "g"(ptr) : "memory");
}

inline void clobber_memory() {
    asm volatile("" : : : "memory");
}

陷阱二：小数组太快，计时噪声大于算法本身

几十个元素的排序可能只有几十到几百纳秒，单次测量几乎没有意义。正确做法是 batch 化，把一批相同规模的排序放到同一个计时窗口里，再除以 batch。

陷阱三：只测一次，拿偶然值当结论

这次套件对每个点都做多次采样，并记录中位数、p5、p95。文章里主要引用中位数，因为它比单次最小值更抗调度抖动。

1.2 这次重跑的测试口径

这次套件覆盖的是：

• 数据类型：int32_t
• 分布：uniform、normal、sorted、reverse、sawtooth、pipe_organ、high_dup
• 规模：64、1024、65536、1000000
• 算法：insertion、heap、merge、quick、introsort、pdqsort、TimSort、radix_lsd、radix_msd、ska_sort、std::sort、std::stable_sort

套件使用固定随机种子 42，小数组走 batch 测量，大数组直接单次计时并重复采样。每轮排序结束后都会检查：

1. 输出是否有序。
2. 输出是否和输入保持同一个 multiset。

二、这次补齐了什么

为了把文章从“描述性 benchmark”变成“可复现 benchmark”，仓库里新增了这些文件：

• bench.cpp：真正执行 benchmark 的 C++20 程序。
• Makefile：构建和一键跑图入口。
• README.md：说明口径、构建方式和复现命令。
• plot.py：把 CSV 渲染成文章里的 SVG。
• results-current-env.csv：这次当前环境的原始结果。

也就是说，现在不是“文章里贴了点代码”，而是仓库里真的有一套可以执行的实验。

三、怎么构建与重跑

真正可执行的命令如下：

cd examples/sort-bench
make

正式跑数：

taskset -c 4 ./sort_bench --csv results-current-env.csv

用当前 CSV 重画文章里的图：

python3 plot.py \
    --csv results-current-env.csv \
    --output ../../post/algorithms/06-sort-bench/benchmark-comparison.svg

如果想换规模：

./sort_bench --sizes 64,4096,262144 --csv custom.csv

四、当前环境与边界

这次重跑环境固定如下：

这里有两个边界必须说清楚：

1. 这次图和表是真实数据，但它们比较的是这套仓库内实现。std::sort / std::stable_sort 是标准库实现；pdqsort、TimSort、radix、ska_sort 是本文配套的参考实现。所以这些结果应理解为“这套实现的表现”，而不是整个算法家族在所有实现下的绝对排名。
2. 当前环境没有 perf，所以旧稿里那些 cache miss、branch miss、IPC 表格全部不保留。没有重测的数据，就不应该继续出现在正文里。

五、当前环境的真实结果

5.1 uniform 随机输入下，不同规模的前三名

这张表足够说明两件事：

• 小规模时，libstdc++ 的 std::sort 是最强 baseline。
• 当数据真的是大规模 int32_t 且分布接近随机时，基数排序会把比较排序甩开一个量级。

5.2 n=1,000,000 时，各分布前三名

这里最值得注意的是：这次真实重跑里，TimSort 对结构化输入非常强，而当前仓库这版 pdqsort 并没有出现“全分布通吃”的表现。

5.3 几个最值得看的对照

下面只挑最常见的几类输入，看几个代表性算法：

另外，heap_sort 在 uniform 1e6 上是 88.122 ms，在 sorted 上是 37.808 ms，在 reverse 上是 42.824 ms，几乎在所有大规模输入里都靠后。这个方向判断和旧稿一致：堆排序更像保底策略，而不是默认首选。

六、这次重跑后，哪些结论还能站住

6.1 还站得住的结论

1. 没有一个算法在所有分布上都最快。 这次环境里，random/high-dup 是 radix 家族赢，sorted/reverse/pipe_organ 是 TimSort 赢。
2. 对大规模 int32_t，radix_lsd 的优势非常实。 在 uniform 1e6 上，它比 std::sort 快约 \(47.153 / 6.019 \approx 7.8\) 倍。
3. TimSort 对有结构的数据极其敏感。 在 sorted 1e6 上，TimSort 0.210 ms，std::sort 4.609 ms，差了约 22 倍。
4. std::sort 仍然是最可靠的比较排序 baseline。 在 uniform 的 64 和 1024 上，它都是第一；在 uniform 1e6 上，它也仍然是比较排序里最快的一档。
5. heapsort 依旧不适合作为默认选择。 它存在的主要工程价值还是给 introsort 兜底最坏情况。

6.2 站不住，或者不能这么写的结论

1. “pdqsort 是通用场景最佳选择” 这句话不能继续保留。 这次真实重跑里，当前仓库这版 pdqsort 在 uniform / normal / high_dup 上都不占优，只在 sorted 上表现很好。
2. 旧稿里的 perf / cache / branch 数字必须删。 当前环境没有 perf，所以这些数字不是这次 bench 产物。
3. 旧稿里关于大对象、并行排序、1e8 规模的具体数字也不该保留。 这次并没有按那个口径重跑，就不要伪装成实测结果。

七、怎么在你的机器上复现

最短路径就是这三条命令：

cd examples/sort-bench
make
taskset -c 4 ./sort_bench --csv results-current-env.csv

重画文章里的 SVG：

python3 plot.py \
    --csv results-current-env.csv \
    --output ../../post/algorithms/06-sort-bench/benchmark-comparison.svg

如果你要修改规模：

./sort_bench --sizes 64,4096,262144 --csv custom.csv

八、当前环境下的选型建议

如果你的问题和这次 bench 的口径接近，也就是单线程、int32_t、内存内排序，那我会给出更保守、也更诚实的一版建议：

1. 随机或接近随机的大规模整数：优先看 radix_lsd。
2. 明显有序、部分有序、run 很长的输入：优先看 TimSort。
3. 只是想要一个稳妥的通用 baseline：先用 std::sort，不要先入为主切到手写 pdqsort。
4. 必须稳定排序，但输入又不是强结构化：先用 std::stable_sort；如果数据本身就带 run，再测 TimSort。
5. heapsort 不要直接选。 让 introsort 在需要时退回堆排序就够了。

最后还是那句老话：永远实测。 但这次至少不再是“文章里说能跑”，而是仓库里真的有代码、真的能跑、真的能产出 CSV 和 SVG 了。

参考文献

1. Musser, D.R. “Introspective Sorting and Selection Algorithms.” Software: Practice and Experience, 27(8), 1997.
2. Peters, O. “Pattern-defeating Quicksort.” arXiv:2106.05123, 2021.
3. McIlroy, P.M. “Optimistic Sorting and Information Theoretic Complexity.” SODA, 1993.
4. Skarupke, M. “ska_sort: A Radix Sort Implementation.” 2016.
5. Peters, T. “TimSort.” CPython source, 2002.
6. Drepper, U. “What Every Programmer Should Know About Memory.” 2007.
7. Fog, A. “Optimizing Software in C++.” 2023.
8. Edelkamp, S., Weiss, A. “BlockQuicksort.” ESA 2016.