土法炼钢 · 系统与基础设施

基数排序：绕开比较下界的代价，从 LSD、American flag sort 到 ska_sort

2025-07-15 | algorithms | #radix-sort #counting-sort #lsd-radix-sort #american-flag-sort #ska-sort #ips2ra #cache #tlb #ieee-754-totalorder

比较下界只约束比较模型，基数排序把代价转移到键长和内存访问上。本文推导代价模型，用缓存模拟与绑核实测解释位宽为何停在 8 到 11 位，并对照 ska_sort、ClickHouse、DuckDB 与 IPS²Ra 说明它何时赢、何时输。