Can you summarize the following document?
        
  外排序的一個例子是外歸併排序(External merge sort),它讀入一些能放在記憶體內的資料量,在記憶體中排序後輸出為一個順串(即是內部資料有序的臨時檔案),處理完所有的資料後再進行歸併。比如,要對900 MB的資料進行排序,但機器上只有100 MB的可用記憶體時,外歸併排序按如下方法操作:  為了增加每一個有序的臨時檔案的長度,可以採用置換選擇排序(Replacement selection sorting)。它可以產生大於記憶體大小的順串。具體方法是在記憶體中使用一個最小堆進行排序,設該最小堆的大小為formula_1。演算法描述如下:  此方法能生成平均長度為formula_2的順串,可以進一步減少訪問外部儲存器的次數,節約時間,提高演算法效率。

  上述例子的外排序有兩個步驟:排序和歸併。我們用一次多路歸併就完成了所有臨時檔案的歸併,而並非按記憶體中的二路歸併那樣,一次歸併兩個子串,耗費formula_3次歸併。外排序中不適用上述方法的原因在於每次讀寫都需要對硬碟進行讀寫,而這是非常緩慢的。所以應該儘可能減小磁碟的讀寫次數。  不過,在上述方法中也存在權衡。當臨時檔案(順串)的數量繼續增大時,歸併時每次可從順串中讀入的資料減少了。比如說,50 GB的資料量,100 MB的可用記憶體,這種情況下用一趟多路歸併就顯得不划算。讀入很多的順串花費的時間佔據了排序時間的大部分。這時,我們可以用多次(比如兩次)歸併來解決這個問題。  這時排序演算法變為下述這樣:  和內排序一樣,高效的外排序所耗的時間依然是formula_4。若利用好現在計算機上GB的記憶體,可使時間複雜度中的對數項增長比較緩慢。

  電腦科學家吉姆·格雷的Sort Benchmark網站用不同的硬體、軟體環境測試了實現方法不同的多種外排序演算法的效率。效率較高的演算法具有以下的特徵:

  外歸併排序法並不是唯一的外排序演算法。另外還有外分配排序,其原理類似於內排序中的桶排序。在歸併排序和桶排序之間存在數學上的某種對偶性。此外還有一些不耗費附加磁碟空間的原地排序演算法。
外排序(External sorting)是指能夠處理極大量資料的排序演算法。通常來說,外排序處理的資料不能一次裝入記憶體,只能放在讀寫較慢的外儲存器(通常是硬碟)上。外排序通常採用的是一種“排序-歸併”的策略。在排序階段,先讀入能放在記憶體中的資料量,將其排序輸出到一個臨時檔案,依此進行,將待排序資料組織為多個有序的臨時檔案。而後在歸併階段將這些臨時檔案組合為一個大的有序檔案,也即排序結果。