对巨大文件中的数据量进行排序，文件名source_data.dat,文件内容类似<key value>
如：
234 78M71639
14 6M88173
1847 736M02472
738 6284M17
排序后:
14 6M88173
234 78M71639
738 6284M17
1847 736M02472
由于待排序文件过大，因此不能将其全部读入内存，故需要借助外部排序算法。
此处外部排序使用归并排序算法, 每个归并段内部排序使用基数排序
-
使用一个读线程将文件内容逐步读入缓冲区
pipe(文件中缓冲区使用线程安全的顺序循环队列实现，大小为1M)。 -
使用一个写线程从缓冲区
pipe中逐行取得数据，形成归并段，生成临时文件。 -
对每个归并段内部使用基数排序，将有序的归并段写入临时文件（如：
./tmp/tmp_r1_0.dat）。 -
归并采用最大100路归并，每100路先归并一次，然后再逐步归并。
-
归并段之间为加快归并效率，使用败者树，寻找最小值
-
归并排序，写入结果文件
source_data_out.dat -
./tmp内是中间临时文件的形成，方便老师查看(若没有./tmp文件夹，请先通过mkdir tmp生成该文件夹)。通过make clean可清除。
-
读写文件速度不匹配，读文件每次读取1024字节到缓冲区，写文件从缓冲区取一行(遇到
\n)写入归并段。【尝试过使用过多个线程读取缓冲区，但是在虚拟机运行时速度不增反降，原因还在找寻。】 -
可能会存在一些资源回收问题，正在逐步调试。
-
对生成的临时文件为方便调试和老师查看没有通过代码自动删除，之后有待补充该函数。
图 1 基数排序数据结构。此处展示的是基数排序第一轮，从key的个位数字看起，bucket[i]会将个位数字为i的条目项用指针连起来。
|
图 2 败者树，用来加快归并段中最小节点的查找。败者树是对树形选择排序的一种变化，它是一颗完全二叉树。每个叶子节点(如：B[0])存放各个归并段在当前位置需要参加归并的记录，其内部节点(如:ltree[1])用来记录左右子数中的“失败者”，从而让胜利者继续比较，一直到根节点。将左右子数中key大的节点定义为失败者，小的为胜利者，则根节点指向的数为最小。
|
Linux环境使用make即可编译。
./sort即可执行，临时文件均生成在./tmp文件夹中。
使用make clean清除所有生成文件。
 | |
 |
 |
| 图 3 运行结果 | |