两种外排序的思路sorting by merging&sorting by distribution

今天我思考了一个问题，顺便翻了翻，对外排序进行了些思考，分享如下：
假定在磁盘上有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可以同时参与计算。但难点是如何让每个桶的数均匀。

补充：软件开发 , C语言 ,

上一个：C技巧：结构体参数转成不定参数
下一个：获得主机的IP和主机名