Bucket Sort

桶排序把数据按值域分到多个桶中，分别排序各桶，再按桶顺序拼接。它利用的是数据分布，而不只是整数值域。

Process

1. 选择桶数量和映射函数 bucket(x)；
2. 单次扫描把元素分配到桶；
3. 对每个桶使用插入排序或其他算法；
4. 依次合并所有桶。

若 $n$ 个元素近似均匀地进入 $k$ 个桶，平均时间可接近 $O(n+k)$；最坏情况下所有元素落入同一桶，复杂度退化为桶内排序的上界。

Design Choices

• 桶边界应与数据分布匹配，等宽桶不一定均衡；
• 桶数量太少会增加桶内排序成本，太多会增加内存和初始化成本；
• 数据偏斜时可采样估计分位点，构造近似等量桶；
• 分布式场景中，桶就是 partition，除了计算量还要控制网络 shuffle 和热点。

桶排序适合已知范围的浮点数、外部排序分区和分布式 range partition；输入分布未知时，应先建立可靠基线再决定是否使用。