一道面试题：4G内存， 100G文件，文件中存放字符串，排序这100G文件字符串数据

内部排序：

内存中可以存放所有待排序的数据，可以使用高效的内部排序来完成例如快速排序，归并排序，堆排序等。

外部排序：

待排序数据过大，内存不能一次全部加载来完成排序。一般采用分段加载内部排序，然后多路合并，产生最后排序结果。

1. 基本实现方式：

      将100G文件分成100份排号为1,2...100，每份1G加载进内存，然后对每份文件采用内部排序来排序，字符串应该有高效的内部排序方式，将排序结果写入到100份文件中，每份文件都是有序的；

      将内存分成3份 1G  1G  2G ，从文件1加载到内存中，从文件2数据到内存中，将这两个文件数据进行归并排序，最终结果写到一个2G文件中，这样依次进行归并排序，可以产生50份2G文件；进行进行归并直到整个文件有序。

      存在的问题： 文件大小的划分，归并排序可以采用多路归并排序。

大神的一个例子，假设有一个含10000 个记录的文件，首先通过10 次内部排序得到10 个初始归并段R1～R10 ，其中每一段都含1000 个记录。然后对它们作两两归并，直至得到一个有序文件为止：



2.多路归并方式：

普通两路归并方式，每次归并两个文件，即从两个文件中选取较小者放入到目标文件中，可以采用K路归并方式，即每一次归并K个文件,即从K个文件中选取较小者放入到目标文件中。增大k可以减少外存信息读写时间，但k个归并段中选取最小的记录需要比较k-1次，为得到u个记录的一个有序段共需要(u-1)(k-1)次，若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为s(n-1)(k-1)。若共有m个归并段，则s=logkm,所以总的比较次数为： (logkm)(k-1)(n-1)=(log2m/log2k)(k-1)(n-1)，而(k-1)/log2k随k增而增因此内部归并时间随k增长而增长了，抵消了外存读写减少的时间，这样做不行，由此引出了“败者树”tree of loser的使用。在内部归并过程中利用败者树将k个归并段中选取最小记录比较的次数降为(log2k)次，使总比较次数为(log2m)(n-1)与k无关。

败者树是完全二叉树，可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls[0]为冠军结点，ls[1]--ls[k-1]为比较结点，ls[k]--ls[2k-1]为叶子结点（同时用另外一个指针索引b[0]--b[k-1]指向）。另外bk为一个附加的辅助空间，不属于败者树，初始化时存着MINKEY的值。

多路归并排序算法的过程大致为：

   1）：首先将k个归并段中的首元素关键字依次存入b[0]--b[k-1]的叶子结点空间里，然后创建败者树，创建完毕之后最小的关键字下标（即所在归并段的序号）便被存入ls[0]中。然后不断循环：

   2）把ls[0]所存最小关键字来自于哪个归并段的序号得到为q，将该归并段的首元素输出到有序归并段里，然后把下一个元素关键字放入上一个元素本来所在的叶子结点b[q]中，调用Adjust顺着b[q]这个叶子结点往上调整败者树直到新的最小的关键字被选出来，其下标同样存在ls[0]中。循环这个操作过程直至所有元素被写到有序归并段里。

以4路归并排序为例，叶子结点存放每个归并段的最小值，然后依次进行比较，失败者成为根节点，成功者进行下一轮比较，5,7 7失败成为根节点，5成功  29,9 29失败为根节点  9成功  5，9下一轮比较  5成功写入输出缓冲区，9失败成为根节点

由于5最小，已经输出，因此把输出元素所在的归并路加载下一个元素，再依次进行比较，有点类似于堆排序，每次将最小的元素输出。