外部排序在本網頁

Question

：

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

合併由此而來一起運行到 先後更大的運行，直到 文件進行排序。

正如我所引用的，我們怎樣才能將結果運行在一起？我們沒有那麼多的記憶。

Answer 1

想象一下，你有數字1 - 9

9 7 2 6 3 4 8 5 1 

而且，我們假設只有3適合在內存中的時間。

所以，你會打破他們分成3塊，每一個分類，儲存在一個單獨的文件中的每個結果：

279 
346 
158 

現在你打開每三個文件的溪流和讀取的第一個值從每個：

2 3 1 

輸出的最低值1，並從該流獲取下一個值，你現在有：

2 3 5 

輸出下一個最小值2，並繼續向前，直到輸出完整的排序列表。

Answer 2

如果您將兩次運行A和B分成更大的運行C，您可以逐行生成逐漸增大的運行，但一次最多隻能讀取兩行。由於該過程是迭代的，並且由於您正在處理數據流而不是完全切割數據，因此您無需擔心內存使用情況。另一方面，磁盤訪問可能會使整個過程變得緩慢 - 但它確實無法擺脫首先完成的工作。