我們爲什麼要用n路合併？與雙向合併相比，它有什麼優勢？

Question

我試圖閱讀關於n向合併的一些文章，但不理解這個概念。我很困惑你爲什麼要使用雙向合併來實現雙向合併？就像你爲什麼要分成數組中的3個部分，對它們進行排序，然後做2路的2份合併，然後2路合併與此第三部分的合併2個部分:)

感謝

Answer 1

「正常「合併排序，您將數組除以2，直到達到深度log2n，然後開始合併。兩個大小爲m的數組的每個合併也將執行2m操作。

，它會給你下面的公式（在時序分析）：

n/2 * 2 + n/4 * 4 + ... 1 * n = n * log2n

現在，如果你做一個三方合併，你將3分割陣列前面的方法不同的是雙重的：

• 深度劃分現在是log3n。
• 合併過程中，不是比較2個元素，而是需要找到3個元素的最小值。

這意味着，在最基本的實現，你會得到這樣一個公式：

n/3 * 2*3 + n/9 * 2*9 + ... 1 * 2*n = 2 * n * log3n

注意2乘以因爲找到最小的三個要素包括2個操作。

漸近地說，這兩個都是Θ(nlogn)。但是，也許（我還沒有嘗試過）在實踐中三路合併排序會因爲其log3n而獲得更好的性能。儘管如此，因爲n = 1000000的log2n僅僅是20，而相同數字的log3n是12.5，我懷疑這種優化是否真的有效，除非n相當大。

---

通過巧妙的實現，k路合併確實可以對合並排序產生很好的影響。這個想法是，一旦你找到最少的k元素，你就已經知道其他不是最小元素的其他元素之間的關係。因此，一旦從其各自的列表中消耗了該最小元素，您只需比較該列表的新值並查找其相對於其餘k-1元素的排序。使用堆，這將是相當微不足道的。

---

一定還會看到Jerry's answer。我同意他的看法，多路合併的真正力量來自處理多個磁盤和並行處理。

Answer 2

當您進行外部排序時，您通常會得到多個要合併的流。例如，假設您需要對一個TB數據進行排序，並且只有（比如說）64千兆字節的RAM。

您通常會通過讀取64千兆字節進行排序，然後將其寫出。對全部TB數據重複一次，爲每個可以一次存儲在內存中的「塊」生成一箇中間文件。有許多方法可以改善這一點，但是通常希望的最好方法是生成每個大約128千兆字節的已排序中間文件。

那給你留下了許多中間文件合併到一起 - 和數量將幾乎肯定會大於2

如果你正在做這樣做定期，你可能有一些相當高端的硬件來做到這一點。如果您已將每個中間文件放在單獨的磁盤驅動器上（並且至少還有一個用於輸出），則幾乎可以一次性合併所有數據，而不是一次只合並兩個數據，從而可以提高速度。這個過程通常是I/O綁定的，因此一次讀取8個磁盤的讀取速度通常是從一次只讀取2個磁盤的速度的4倍左右（儘管這取決於您的輸出磁盤具有多少帶寬，這可能並非如此）。通過避免創建更多的中間文件（這將需要進一步合併），您的整體速度可能會提高一個更大的因素。