基数排序：绕开比较下界的代价，从 LSD、American flag sort 到 ska_sort
比较下界只约束比较模型，基数排序把代价转移到键长和内存访问上。本文推导代价模型，用缓存模拟与绑核实测解释位宽为何停在 8 到 11 位，并对照 ska_sort、ClickHouse、DuckDB 与 IPS²Ra 说明它何时赢、何时输。
radix-sort 标签归档
共 3 篇文章 · 返回首页
并行排序：排序网络、并行归并、样本排序与 GPU 基数排序
用 work/span 计数解释并行排序为何难以线性加速：串行归并与串行划分把并行度压在个位数，并行归并、Merge Path 与样本排序各自如何突破；再对照 libstdc++、oneTBB、Rayon、CUB 源码看生产实现的真实选择。
排序基准测试：比较次数、分支预测与输入分布
在 GCC 16 上对 9 种 int32 排序做精确比较计数与绑核计时（8 种输入分布、3 个进程取中位数）：比较次数预测不了耗时，分支预测与输入结构决定排名；反复排序同一数组会把小数组耗时低估 2 到 6 倍。