algorithm - 关于多遍排序算法

Question

我正在阅读Jon Bentley 的Programming Pearls（参考）。

这里作者提到了各种排序算法，如归并排序、多遍排序。

问题：

1. 合并排序算法如何通过读取输入文件一次并使用工作文件并只写入一次输出文件来工作？

2. 作者如何通过只向输出文件写入一次并且没有工作文件来表示 40 pass ie multipass 排序算法的工作原理？

有人可以用一个简单的例子来解释上面的内容，比如有内存来存储 3 位数字和 10 位数字来存储，例如9,0,8,6,5,4,1,2,3,7

Answer 1

这是 Jon Bentley 的 Programming Pearls, 2nd Edn (1999) 的第 1 章，这是一本很棒的书。第一版的等效示例略有不同；多通道算法仅对数据进行了 27 次传递（可用内存较少）。

Jon Bentley 描述的排序具有特殊的设置约束。

• 文件最多包含 1000 万条记录。
• 每条记录是一个 7 位数字。
• 没有与记录关联的其他数据。
• 必须进行排序时，只有 1 MiB 的可用内存。

问题 1

输入文件的单次读取会从输入中读取尽可能多的行，以适应内存，对数据进行排序，然后将其写入工作文件。冲洗并重复，直到输入文件中没有更多数据。

然后，通过读取工作文件并将排序的内容合并到单个输出文件中来完成该过程。在极端情况下，可能需要创建新的、更大的工作文件，因为程序无法一次读取所有工作文件。如果发生这种情况，您将安排最后一次传递具有可以处理的最大输入数，并让中间传递合并适当数量的文件。

这是一种通用算法。

问题2

这是利用数据的特殊属性的地方。由于数字是唯一的并且范围有限，算法可以第一次读取文件，从范围的前四十个中提取数字，排序并写入；然后它提取范围的第二个四十，然后是第三个，...，然后是最后四十个。

这是一种特殊用途的算法，利用了数字的性质。