我已经了解外部排序的作用，它的用途；但是我有一个关于合并极端情况的问题。
外部排序 第一个答案解释了外部排序合并的工作原理。但如果：
假设我们有 10 个单位的内存大小，我们想要对 50 个单位的文件进行排序
首先，我们将文件分成 5 个运行（每个运行 10 个单元）并单独排序
其次，我们必须将它们与 4-way merge 合并
和 10/4 = 2.5 ~ 2; 我们从每次运行中取出 2 个单元（块），将它们放入内存并开始合并；
那么实际的问题是：如果（假设）第三次运行的第二和第三块有
比其他运行的第一块更小的元素？合并过程会成功吗？
如果我对我的理解有错误，任何解释都会有所帮助。
好吧，在任何文件中都有更小/更大的元素是没有问题的。以下是外部排序过程的示例：
您的初始数据：
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。
由于第三个文件和最后一个生成的文件肯定都已排序，因此您可以顺序扫描两个文件中的数据，将条目合并为一个唯一的结果。