sorting 标签归档 | 土法炼钢 · 系统与基础设施

算法工程索引

汇总本站算法工程相关文章，覆盖排序、哈希、树、字符串、近似数据结构、SIMD、随机化与编译器相关算法。

对照 CPython 与 OpenJDK 源码拆解 TimSort 的 run 检测、minrun、galloping 与合并，梳理 2015 年栈不变量 bug 和改用 Powersort 的原因；比较次数来自与 CPython 逐次一致的 C 移植。

对照 orlp/pdqsort 源码与 Peters 论文，拆解 pdqsort 在 introsort 上的四处改动；用与参考实现比较次数逐次一致的 C 移植和 McIlroy 对抗输入实测，并梳理 Boost、Rust、Go、libc++ 各自采用了哪些部分。

用 work/span 计数解释并行排序为何难以线性加速：串行归并与串行划分把并行度压在个位数，并行归并、Merge Path 与样本排序各自如何突破；再对照 libstdc++、oneTBB、Rayon、CUB 源码看生产实现的真实选择。

在 GCC 16 上对 9 种 int32 排序做精确比较计数与绑核计时（8 种输入分布、3 个进程取中位数）：比较次数预测不了耗时，分支预测与输入结构决定排名；反复排序同一数组会把小数组耗时低估 2 到 6 倍。

把 TimSort、pdqsort、radix sort、external sort、parallel sort 与 benchmark 串成一条阅读路径。先读哪篇、什么时候选哪种排序，这一页讲清。