今天我思考了一個問題，順便翻了翻，對外排序進行了些思考，分享如下：
假定在磁盤上有16個數字，而內存只能容下4個數進行排序，那麼歸並的排序和桶排序有怎樣的區別呢？其實各有千秋。歸並的排序無疑是最常用的，思想簡單，但最後一步多路歸發揮多核優勢有困難，桶排序的方法充分發揮多核優勢，難點在於如何讓桶內distributing進來的關鍵字數量一致，詳細可參考我曾推薦的這本書。
為了便於理解我舉了個例子：
input:1 4 2 8 12 11 3 6 9 40 28 27 21 7 6 3
output：
sorting by merge
(1)分段 (2)內排序 （3）多路歸並（敗者樹）
1 4 2 8 1 2 4 8
12 11 3 6 3 6 11 12
9 40 28 27 9 27 28 40 1 2 3 3 4 6 6 7 8 9 11 12 21 27 28 40
21 7 6 3 3 6 7 21
(1)其實是什麼也不做
磁盤ＩＯ量0次
input:1 4 2 8 12 11 3 6 9 40 28 27 21 7 6 3
output：
(2)
磁盤ＩＯ量16*2=32字節（讀16字節，寫16字節）
input:1 2 4 8 3 6 11 12 9 27 28 40 3 6 7 21
output：
(3)
磁盤ＩＯ量讀16*2 = 32字節
input: 1 2 4 8 3 6 11 12 9 27 28 40 3 6 7 21
output：1 2 3 3 4 6 6 7 8 9 11 12 21 27 28 40
如果有4個CPU,第一、二個階段4個CPU可以同時參與計算，第三階段最多可有2個CPU可參與計算，一個從output開頭寫，一個從output結尾寫，兩頭往中間寫，直到滿。文件可以采用內存映射的方式，實現兩頭往中間寫。
sorting by distribution
(1)分桶 (2)內排序（排序後，則按桶的順序自然有序）
1 2 3 3 1 2 3 3
4 6 7 6 4 6 6 7
8 9 12 11 8 9 11 12
40 28 27 21 21 27 28 40
(1)
磁盤ＩＯ量16*2 = 32字節
input: 1 4 2 8 12 11 3 6 9 40 28 27 21 7 6 3
output：1 2 3 3 4 6 7 6 8 9 12 11 40 28 27 21
(2)
磁盤ＩＯ量16*2 = 32字節
input: 1 4 2 8 12 11 3 6 9 40 28 27 21 7 6 3
output：1 2 3 3 4 6 6 7 8 9 11 12 21 27 28 40
如果有4個CPU,第一、二個階段4個CPU可以同時參與計算。但難點是如何讓每個桶的數均勻。
