轉自http://hawstein.com/posts/9.4.html
k路歸并可以參考leetcode題：http://blog.csdn.net/todorovchen/article/details/26366553
當面試官說到2GB檔案的時候，他其實就是在暗示你， 他并不希望一次性把所有的資料都載入記憶體。這樣子的話，我們要怎麼做呢？ 我們每次就将部分資料載入記憶體就好了。
算法：
首先我們要了解，可以用的記憶體有多大？假設我們有X MB的記憶體可用。
- 我們将檔案分為K份，其中X*K=2GB。每次取其中一份載入到記憶體中， 用O(nlog n)的算法排序，然後再儲存到外部檔案。
- 載入下一份并排序
- 當我們将K份小檔案都排好序，合并它們。
上面的算法就是外排序，步驟3又稱為N路歸并。
使用外排序是由于資料太大了，無法一次全部加載到記憶體中，是以需要借助磁盤進行存儲， 每次隻從磁盤中加載一部分資料進入記憶體，進行排序。