内存受限下多文件合并排序：堆外排与桶排序的时间复杂度对比

时间复杂度是否具备可比性 #

二者完全具备可比性，核心开销都可以拆分为CPU计算开销、I/O开销两类分别计算：

• 外部排序的总CPU复杂度为O(N log N)：其中单小文件排序总开销为O(N log M)（N为总元素数，M为单小文件元素数），k路堆合并开销为O(N log k)（k为小文件总数），二者合并后等价于O(N log N)。I/O层面全为顺序读写，总读写次数为2次全量（读所有小文件排序+写排序后的小文件，再读排序后的小文件+写最终文件）。
• 均匀分布前提下的桶排序CPU复杂度为O(N log B)（B为单桶预设元素数）：分桶操作开销为O(N)，所有桶排序总开销为O(N log B)，当B远小于N时，CPU开销确实低于外部排序。但I/O开销远高于前者。

外部排序是否始终更优 #

并非始终更优，仅在多数通用场景下表现更稳定：

• 若数值确实均匀分布、你可以提前拿到全局极值、存储空间足够、且存储介质随机写性能足够高（比如高端SSD/傲腾），桶排序的总耗时可能低于外部排序。
• 若数值分布倾斜、无法提前拿到全局极值、或使用机械硬盘存储，外部排序的性能会显著优于桶排序。

桶排序容易忽略的额外耗时点 #

你当前的流程设计漏了几个非常影响性能的环节：

• 全局极值扫描开销：要计算桶的数量首先需要知道全量数据的最大值和最小值，如果你没有提前预处理过这个信息，需要额外遍历一次所有小文件，增加一次全量读I/O开销，外部排序无此步骤。
• 分桶阶段的随机写开销：外部排序的所有I/O都是顺序读写，而桶排序分桶时，每批100个元素可能对应多个不同桶，需要给多个桶文件分别追加写入，属于典型的随机写操作。机械硬盘下随机写性能比顺序写低100倍以上，SSD下随机写性能也比顺序写低数倍，这是最容易被忽略的性能损耗点。
• 大量小桶的文件管理开销：如果单桶元素数设置过小，会生成上万甚至几十万个临时桶文件，超过操作系统单进程文件句柄上限后，需要频繁开关文件，会带来大量额外的系统调用开销。
• 桶拼接的额外I/O开销：所有桶排序完成后，你需要顺序读取所有桶文件再写入最终文件，这额外增加了一次全量读写I/O，而外部排序合并阶段直接写最终文件，无此开销。

你之前认为桶排序仅临时存储空间更高的判断不准确，它的实际I/O开销多数情况下远高于外部排序，仅在非常苛刻的特定场景下才能体现出性能优势。

内容的提问来源于stack exchange，提问作者404error