因為原來的文章沒人回，所以只好開了這個文章，希望看的人多些，給一下解答。

原來的文章為面試題之10億正整數問題，其實其基本都是從《編程珠璣》上面修改而來的，只是問題的規模變大了而已。但是在仔細研究《編程珠璣》中的解法時，發現是不是因為說得太簡略，對于其中介紹的多通道排序并不是很理解。

這里因為前面的文章已經將問題介紹得比較清楚了，所以就簡單將整理之后的問題描述如下：

【整理之后，精確的問題陳述】

輸入：

所輸入的是一個文件，至多包含n個正整數，每個正整數都要小于n，這里的n為10^7。如果輸入時某一個整數出現了兩次，就會產生一個致命的錯誤。這些整數與其他任何數據都不關聯。

輸出：

以增序形式輸出經過排序的整數列表。（這里應該補充一下是文件形式嗎？）

約束：

至多（大概）只有1MB的可用主存，但是可用磁盤空間非常充足。運行時間至多只允許幾分鐘，最適宜的時間大概為10秒鐘。

作者一共介紹了3種解法，一是歸并排序，二是多通道排序，三是叫做精彩排序的方法。

關于歸并排序，并沒有什么問題，使用分而治之的方法，將輸入文件分為若干段，然后對每一段使用內排序，并輸出到中間文件中，最后對這些中間文件進行合并，生成一個最終排序好的輸出文件。

這里對輸入文件會讀取一次，對中間文件會操作多次（讀取和寫入），對輸出文件會寫入一次。

但是對于多通道排序，從作者的描述來看，似乎和歸并排序差不多，沒太理解明白，為什么作者說，我們不需要使用中間磁盤文件，但是需要多次讀取輸入文件。

對于多通道排序，作者的描述如下：

因為一共有10000000個整數，而1M中我們使用250000個號碼存儲，所以需要使用40個通道。

第一個通道中將0到249999之間的任意整數讀到內存中，并對這250000個整數進行排序，然后將它們寫入輸出文件中。

第二個通道對250000到499999之間的整數進行排序，然后也是同樣寫入輸出文件中。

依次類推，直到第40個通道。

第40個通道將排序9750000到9999999之間的整數，然后寫入輸出文件中。

注意，這里意思是輸出文件是同一個文件。

快速排序在主存中相當有效，它只需要20行代碼。因此整個程序只需1到2頁的代碼即可實現，并且該程序還有一個令人滿意的特性，即我們不必擔心使用中間磁盤文件的問題。

40個通道的算法不使用中間文件，需要多次讀取輸入文件，但只進行一次輸出文件的寫入操作。

這里就有些不太明白，為什么不用中間文件，不用中間文件的話，具體是如何操作的？

多通道排序，其英文為multi-pass sort，或者multiple pass sort。從查到的資料來看，似乎數據庫中使用較多，在一些Oracle的教程中，有cache sort, one-pass sort和multi-pass sort的說法，但是一是不清楚這里所說的多通道排序是否是數據庫中的這個，還有就是從數據庫中那里來看，也似乎沒有說不需要使用中間文件。

大家有沒有了解這個的呢？能否解釋解釋，想得頭疼~~ 

關于sort搜索到的資料，in memory sort就是cache sort.

in memory sort Everything fits in memory, no disk is needed, everything done in ram. 

one pass sort We read some amount of data and sort it, the sort workarea fills up, we write that to disk. We do it again (read more, sort it) - this too spills to disk. We do this over and over until we've read the entire set of data and sorted each of the chunks. Now we need read a bit of each of the chunks we've sorted on disk and start returning data from there. In the one pass sort, we can read a bit of each chunk and start returning data. If we cannot read a bit of EVERY chunk then.... 

we are in the realm of the multi-pass sort. We read and merge the first few chunks - resulting in a new set. We read and merge another set of chunks - resulting in a new set. And so on - until we've processed all of the output from the first pass and created a "second pass" of more merged (more sorted) data. Then we merge those in the sort area and start returning data.  

參考地址：http://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:1308127400346936009