外部排序 - 特定情況下的合併問題

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

由於兩個第三個文件，最後生成的文件是肯定排序，你可以依次掃描從兩個文件中的數據，合併項目成獨特的結果。