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

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]

现在我的问题是,如果它们不适合内存,我如何将这些文件中的块合并到较大的文件中呢？杰弗里麦康奈尔写道,我需要阅读半块并将它们合并到下一个文件C和D.

但我得错了序列:

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

有人可以提供分步说明的例子吗？

PS:我理解如何通过读取文件来合并数字,但是如何使用内存缓冲区来减少I/O操作呢？

Answer 1

我想经过这么长时间你一定得到了答案.但我仍然提供一些示例链接来帮助其他人来解决这个问题.

注:寻找到这个环节之前,您应该有关于一个想法堆数据结构来看看双向排序的实例和多路外部排序的例子,你会得到一个外部排序算法的实现的一个完整的想法

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可以有多个数字.通过mergind C和D,您将获得一个新的块E,它将成为最终的排序文件.

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

Answer 3

您将同时遍历文件.

从每个文件的开头开始,继续选择哪个文件的元素不大于另一个文件的元素(即小于或等于),将该元素输出到新文件并增加迭代器.

从你上次的陈述来看,目前还不清楚你是否已经知道这样做了,但这就是你需要做的全部,因为:

因此对于:

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].