外部合并排序算法是如何工作的？

Question

我正在尝试理解外部合并排序算法是如何工作的（我看到了相同问题的一些答案，但没有找到我需要的东西）。我正在阅读Jeffrey McConnell的《算法分析》一书，我正在尝试实现那里描述的算法。

例如，我有输入数据：3,5,1,2,4,6,9,8,7，我只能将4个数字加载到内存中。

我的第一步是以4个数字块读取输入文件，在内存中对它们进行排序，然后将其中一个写入文件A和文件B。

我得到：

A:[1,2,3,5][7]  
B:[4,6,8,9]

现在我的问题是，如果这些文件中的块不适合内存，我如何将它们合并到更大的文件中？Jeffrey McConnell写道，我需要读取一半的块并将它们合并到下一个文件C和D。

但我搞错了顺序：

C:[1,2,4,6,3,8,5,9]
D:[7]

有人能提供一个循序渐进的例子吗？

PS：我了解如何通过从文件中读取逐个数字进行合并，但如何使用内存缓冲区来减少I/O操作？

Answer 1

您将同时遍历文件。

只需从每个文件的开头开始，不断选取不大于（即小于或等于）另一个文件的元素，将该元素输出到新文件并增加迭代器。

从你上次的陈述来看，不清楚你是否已经知道要这么做，但这就是你需要做的，因为：

>

您只需要读取每个文件一次，因为在此过程中，您可以将文件保持在正确的位置打开，这样您就不需要再次读取整个文件才能到达正确的位置。

因此，对于：

A:[1,2,3,5]
B:[4,6,8,9]

您将从每个文件中的第一个元素开始-1和4。

1较小，因此您可以将其输出到新文件，然后转到2。

2小于4，因此您可以输出该值并转到3。

3小于4，因此您可以输出该值，然后转到5。

4小于5，因此您可以将其输出并转到6。

5比6小，所以您可以输出它，然后到达A的末尾。

现在只需输出B的其余部分：6,8,9。

这将为您提供[1,2,3,4,5,6,8,9]。

Answer 2

首先，通过对4个数字的部分进行排序，你应该得到3个块。

A:[1,2,3,5]  
B:[4,6,8,9]
C:[7]

然后，您将读取每个文件的一半（忽略C，因为它不适合）并合并它们。因此，您将加载到内存{[1,2]，[4,6]}。您将进行一次临时合并，并将结果写入一个新的块D中：

Compare 1 and 4 -> D:[1]
Compare 2 and 4 -> D:[1, 2]

现在RAM中的A部分完成了合并，所以现在您必须将其后半部分放入内存中。现在您的内存将有{[3,5]，[4,6]}。

Compare 3 and 4 -> D:[1, 2, 3]
Compare 5 and 4 -> D:[1, 2, 3, 4]
Compare 5 and 6 -> D:[1, 2, 3, 4, 5]

所有块A都被合并了，所以现在只需将B的其余部分附加到D中

D:[1,2,3,4,5,6,8,9]

现在，你必须对块C和块D进行同样的处理。记住，在另一个例子中，C可以有多个数字。通过合并C和D，您将得到一个新的块E，它将是最终排序的文件。

另外，请注意，在一个更大的示例中，您可能需要更多的合并阶段。例如，如果您有20个数字要排序，您将创建5个4个数字的块，然后每次合并和合并其中两个，生成2个8个数字的块（加上4个数字中的一个额外的），然后将较新的块合并为16个数字中的一个，依此类推。

Answer 3

我想经过这么长时间，你一定得到了答案。但我仍在提供一些示例链接，以帮助遇到这个问题的其他人。

注意：在研究此链接之前，您应该对堆数据结构有一个想法，看看双向排序示例和多路外部排序示例，您将获得外部排序算法实现的完整想法