algorithm - 如何对大文件进行排序(不适合 RAM)

Question

假设有一个算法 X 需要 2 个步骤才能最终输出到文件。

1. 收集数据
2. 排序数据

我们还假设收集的数据太大而无法保存在 RAM 中，因此在第 2 步执行操作之前将其写入文件。

例如，以步骤 1 输出的包含数字的 500GB 文件为例。每行一个数字。第 2 步必须按升序对行进行排序。

第 2 步如何在不读取整个输入文件的情况下有效地对数字进行排序？

Answer 1

最有效的方法是将交换空间增加 500 GB 并进行一次排序，让操作系统内存管理器处理缓存。

另一种方法是将数据分成适合的部分，比如 250 个 2GB 的文件。对每一个进行排序，然后对结果进行归并排序。