读取文件填充数据时排序还是填充完成后排序效率更高？

单算法边读边排方案效率确实更高 #

相比先统计数据量再选排序算法的方案，单算法边读边排的性能优势非常明显：

• 省去不必要的开销：如果为了统计数量额外扫描一次文件，磁盘IO耗时会直接翻倍；哪怕是边读边存数据同时计数，也多了维护双算法逻辑、判断切换阈值的成本，而且人工设定的阈值很难适配所有硬件和运行环境，很容易出现边界场景的性能劣化。
• 支持IO和计算重叠：不需要等所有数据全部加载到内存再开始排序，读取文件的IO等待时间可以用来处理已经读到的整数做排序预处理，整体耗时更短。
• 目前成熟的自适应排序算法已经完全可以覆盖10到20万的输入规模差，不需要额外做多算法适配。

最适合的排序算法是Timsort #

这个场景下最优的选择是Timsort，核心原因有三个：

• 自适应特性天然适配波动输入：Timsort是插入排序和归并排序的混合自适应算法，短输入自动走插入排序分支，长输入走归并排序分支，不需要手动做算法切换。10个元素的小文件场景下，它的性能和手写插入排序几乎没有差异；20万个元素的大文件场景下，也能保持稳定的O(nlogn)时间复杂度，不会出现快速排序最坏O(n²)的退化问题。
• 稳定排序符合需求：Timsort是稳定排序，相同数值的整数会保留输入时的相对顺序，刚好可以保证同一个值对应的多个行号按实际出现顺序排列，匹配输出要求。
• 无需手动实现，性能有保障：目前绝大多数主流编程语言的标准库默认排序都是优化过的Timsort实现，直接调用标准库的sort()方法就能拿到工业级的优化性能，不需要自己造轮子。

内容的提问来源于stack exchange，提问作者Othman H