外排序

外排序（External sorting）是指能夠處理極大量數據的排序算法。通常來說，外排序處理的數據不能一次裝入內存，只能放在讀寫較慢的外存儲器（通常是硬盤）上。外排序通常採用的是一種「排序-歸併」的策略。在排序階段，先讀入能放在內存中的數據量，將其排序輸出到一個臨時文件，依此進行，將待排序數據組織為多個有序的臨時文件。而後在歸併階段將這些臨時文件組合為一個大的有序文件，也即排序結果。

外歸併排序

外排序的一個例子是外歸併排序（External merge sort），它讀入一些能放在內存內的數據量，在內存中排序後輸出為一個順串（即是內部數據有序的臨時文件），處理完所有的數據後再進行歸併。^[1]^[2]比如，要對900 MB的數據進行排序，但機器上只有100 MB的可用內存時，外歸併排序按如下方法操作：

讀入100 MB的數據至內存中，用某種常規方式（如快速排序、堆排序、歸併排序等方法）在內存中完成排序。
將排序完成的數據寫入磁盤。
讀入每個臨時文件（順串）的前10 MB（ = 100 MB / (9塊 + 1)）的數據放入內存中的輸入緩衝區，最後的10 MB作為輸出緩衝區。（實踐中，將輸入緩衝適當調小，而適當增大輸出緩衝區能獲得更好的效果。）
執行九路歸併算法，將結果輸出到輸出緩衝區。一旦輸出緩衝區滿，將緩衝區中的數據寫出至目標文件，清空緩衝區。一旦9個輸入緩衝區中的一個變空，就從這個緩衝區關聯的文件，讀入下一個10M數據，除非這個文件已讀完。這是「外歸併排序」能在主存外完成排序的關鍵步驟 -- 因為「歸併算法」(merge algorithm)對每一個大塊只是順序地做一輪訪問(進行歸併)，每個大塊不用完全載入主存。

為了增加每一個有序的臨時文件的長度，可以採用置換選擇排序（Replacement selection sorting）。它可以產生大於內存大小的順串。具體方法是在內存中使用一個最小堆進行排序，設該最小堆的大小為 $M$ 。算法描述如下：

初始時將輸入文件讀入內存，建立最小堆。
將堆頂元素輸出至輸出緩衝區。然後讀入下一個記錄：
1. 若該元素的關鍵碼值不小於剛輸出的關鍵碼值，將其作為堆頂元素並調整堆，使之滿足堆的性質；
2. 否則將新元素放入堆底位置，將堆的大小減1。
重複第2步，直至堆大小變為0。
此時一個順串已經產生。將堆中的所有元素建堆，開始生成下一個順串。^[3]

此方法能生成平均長度為 $2M$ 的順串，可以進一步減少訪問外部存儲器的次數，節約時間，提高算法效率。

附加的步驟

上述例子的外排序有兩個步驟：排序和歸併。我們用一次多路歸併就完成了所有臨時文件的歸併，而並非按內存中的二路歸併那樣，一次歸併兩個子串，耗費 $\log _{2}n$ 次歸併。外排序中不適用上述方法的原因在於每次讀寫都需要對硬盤進行讀寫，而這是非常緩慢的。所以應該儘可能減小磁盤的讀寫次數。

不過，在上述方法中也存在權衡。當臨時文件（順串）的數量繼續增大時，歸併時每次可從順串中讀入的數據減少了。比如說，50 GB的數據量，100 MB的可用內存，這種情況下用一趟多路歸併就顯得不划算。讀入很多的順串花費的時間佔據了排序時間的大部分。這時，我們可以用多次（比如兩次）歸併來解決這個問題。

這時排序算法變為下述這樣：

第一步不變。
將小的順串合併為大一些的順串，適當減小順串的數目。
將剩餘的大一些的順串歸併為最終結果。

和內排序一樣，高效的外排序所耗的時間依然是 $O(n\log n)$ 。若利用好現在計算機上GB的內存，可使時間複雜度中的對數項增長比較緩慢。

優化性能

計算機科學家吉姆·格雷的Sort Benchmark（頁面存檔備份，存於互聯網檔案館）網站用不同的硬件、軟件環境測試了實現方法不同的多種外排序算法的效率。效率較高的算法具有以下的特徵：

並行計算
- 用多個磁盤驅動器並行處理數據，可以加速順序磁盤讀寫。^[4]
- 在計算機上使用多線程，可在多核心的計算機上得到優化。
- 使用異步輸入輸出，可以同時排序和歸併，同時讀寫。
- 使用多台計算機用高速網絡連接，分擔計算任務。^[5]
提高硬件速度
- 增大內存，減小磁盤讀寫次數，減小歸併次數。
- 使用快速的外存設備，比如15000 RPM的硬盤或固態硬盤。
- 使用性能更優良個各種設備，比如使用多核心CPU和延遲時間更短的內存。
提高軟件速度
- 對於某些特殊數據，在第一階段的排序中使用基數排序。
- 壓縮輸入輸出文件和臨時文件。

其他算法

外歸併排序法並不是唯一的外排序算法。另外還有外分配排序，其原理類似於內排序中的桶排序。在歸併排序和桶排序之間存在數學上的某種對偶性。^[6]此外還有一些不耗費附加磁盤空間的原地排序算法。

外部連結

參考

^ Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998, ISBN 0-201-89685-0, Section 5.4: External Sorting, pp.248–379.
^ * Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures, H. Freeman & Co., ISBN 0-7167-8042-9.
^ 張銘、王騰蛟、趙海燕. 数据结构与算法. 北京: 高等教育出版社. 2008: pp.246–248. ISBN 978-7-04-023961-4.
^ Nikolas Askitis, OzSort 2.0: Sorting up to 252GB for a Penny （頁面存檔備份，存於互聯網檔案館）
^ Rasmussen et al., TritonSort （頁面存檔備份，存於互聯網檔案館）
^ J. S. Vitter, Algorithms and Data Structures for External Memory （頁面存檔備份，存於互聯網檔案館）, Series on Foundations and Trends in Theoretical Computer Science, now Publishers, Hanover, MA, 2008, ISBN 978-1-60198-106-6.

[1] Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998, ISBN 0-201-89685-0, Section 5.4: External Sorting, pp.248–379.

[2] * Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures, H. Freeman & Co., ISBN 0-7167-8042-9.

[3] 張銘、王騰蛟、趙海燕. 数据结构与算法. 北京: 高等教育出版社. 2008: pp.246–248. ISBN 978-7-04-023961-4.

[4] Nikolas Askitis, OzSort 2.0: Sorting up to 252GB for a Penny （頁面存檔備份，存於互聯網檔案館）

[5] Rasmussen et al., TritonSort （頁面存檔備份，存於互聯網檔案館）

[6] J. S. Vitter, Algorithms and Data Structures for External Memory （頁面存檔備份，存於互聯網檔案館）, Series on Foundations and Trends in Theoretical Computer Science, now Publishers, Hanover, MA, 2008, ISBN 978-1-60198-106-6.

[1]

[2]

[3]

[4]

[5]

[6]