外部排序 - 特定情况下的合并问题

Question

我已经理解外部排序是干什么的，干什么用的;但我在脑海里想了解一个合并极端情况的问题。

external sorting第一个答案解释了外部排序合并的工作原理。但是，如果：

假设我们有10个单位的内存大小，我们想排序50个单位的文件

首先我们切片文件到5次运行（它们中的每10个单位），并且个别排序

秒我们必须合并它们与4路合并

和10/4 = 2.5〜2;我们从每次运行中取2个单位（块），将它们放入内存中，我们开始合并;

然后实际的问题是：如果有什么第二，（假设）第三次运行的第三块具有比其他运行的第一大块

较小的元素？合并过程是否会成功？

如果我对我的理解有任何错误，任何解释都会有帮助。

Answer 1

好吧，在任何文件中都有更小/更大的元素没有问题。下面是外部排序过程的例子：

你的初始数据：

data = [2, 5, 3, 7, 1, 6, 4, 8, 9] 

考虑你只有3个单位的内存，你有以下的碎片，和排序的结果：

d1 = [2, 5, 3] -> sorting -> d1 = [2, 3, 5] 
d2 = [7, 1, 6] -> sorting -> d2 = [1, 6, 7] 
d3 = [4, 8, 9] -> sorting -> d3 = [4, 8, 9] 

当你有三个可用的单位，您可以在同一时间三个碎片阅读，所以，你必须：

d = [], d1 = [2, 3, 5], d2 = [1, 6, 7], d3 = [4, 8, 9] -> min(d1, d2, d3) = 1 
d = [1], d1 = [2, 3, 5], d2 = [6, 7], d3 = [4, 8, 9] -> min(d1, d2, d3) = 2 
d = [1, 2], d1 = [3, 5], d2 = [6, 7], d3 = [4, 8, 9] -> min(d1, d2, d3) = 3 
d = [1, 2, 3], d1 = [5], d2 = [6, 7], d3 = [4, 8, 9] -> min(d1, d2, d3) = 4 
d = [1, 2, 3, 4], d1 = [5], d2 = [6, 7], d3 = [8, 9] -> min(d1, d2, d3) = 5 
d = [1, 2, 3, 4, 5], d1 = [], d2 = [6, 7], d3 = [8, 9] -> min(d1, d2, d3) = 6 
d = [1, 2, 3, 4, 5, 6], d1 = [], d2 = [7], d3 = [8, 9] -> min(d1, d2, d3) = 7 
d = [1, 2, 3, 4, 5, 6, 7], d1 = [], d2 = [], d3 = [8, 9] -> min(d1, d2, d3) = 8 
d = [1, 2, 3, 4, 5, 6, 7, 8], d1 = [], d2 = [], d3 = [9] -> min(d1, d2, d3) = 9 
d = [1, 2, 3, 4, 5, 6, 7, 8, 9], d1 = [], d2 = [], d3 = [] -> [] 

您可能会关注的是，当您有足够的限制以允许您不从每个文件中读取至少一个元素，或者即使决定只是从给定文件中读取更多元素，将另一个文件留下读。

这与上面的过程相同，唯一不同的是，在读取两个文件并合并它们之间的数据之后，您必须从第三个文件和文件生成，这是文件1的合并和2

由于两个第三个文件，最后生成的文件是肯定排序，你可以依次扫描从两个文件中的数据，合并项目成独特的结果。