外部存儲器合併排序

Question

任何人都可以指出我對外部存儲器Mergesort的一個很好的參考嗎？我已閱讀維基頁面，但無法準確理解它。動畫可能有幫助，但我似乎無法找到一個。

基本上，我知道你在磁盤上有一定數量的塊，並且你可以在內存中容納一定數量的塊。假設你有32塊磁盤和4塊內存。在第一遍中，您一次將4個塊讀入內存，將它們排序在內存中，然後將它們寫回磁盤。所以在這一點上，你有8塊分4塊運行。合併工作如何？由於我在內存中有4塊（假設我還有一塊用於輸出），我認爲我應該能夠一次合併這8個運行中的4個，然後合併接下來的4個運行。然後在最後一遍我想合併整個事情。但是，你不必每次都從磁盤讀取每個塊嗎？那麼這怎麼不會成爲n^2解決方案呢？

Answer 1

我想我現在明白了。當你合併時，你仍然必須讀取磁盤上的所有塊（讓我們稱之爲B），但是你不必閱讀它們B次。你只能讀它們B日誌B次。