问外部排序

EN

想象一下你的数字是1-9

9  7  2  6  3  4  8  5  1

让我们假设一次内存中只有3块。

因此，您可以将它们分解为3块，并对每个块进行排序，将每个结果存储在一个单独的文件中：

279
346
158

现在，您可以将这三个文件中的每一个作为流打开，并从每个文件中读取第一个值：

2 3 1

输出最低值1，并从该流中获取下一个值，现在有：

2 3 5

输出下一个最低值2，然后继续，直到输出整个排序列表为止。

如果您将两次运行A和B处理为更大的运行C，则可以逐行生成更大的运行，但一次最多只能读取2行。因为这个过程是迭代的，而且您正在处理数据流，而不是完整的数据切分，所以您不需要担心内存的使用。另一方面，磁盘访问可能会使整个过程变慢--但它肯定比一开始就不能完成工作要好。