问题：机器内存100M，想对100G的外部(硬盘)数据进行排序

思路：几乎所有人看到这个问题第一反应都是分割，先这样，然后那样，再那样，最后那样，懵懵懂懂的说不清楚。

我提供两种方法：

一、先拆分再归并

100G数据分成20M一份（本来想分成３０的，可惜数学不好），这样得到5000个分片（假装算对了）

5000个分片分别叫s0-1   s0-2   s0-3  s0-4 .....................s0-5000

第１轮排序

先把s0-1  s0-2召唤到内存进行排序，输出到外部分别为s1-1   s1-2

然后同理再把s0-3  s0-4为一组 s0-5  s0-6一组.......排出s1-3   s1-4    s1-5  s1-6.......

注意，排完之后第s1-1和s1-2，s1-3和s1-4，s1-5和s1-6.......组之间是无序的，但是组内是有序的

第２轮排序

把s1-1和s1-3召唤到 内存排序，其中一个排到末尾了则要输出到外部为s2-1 ，然后把它组内的下个小伙伴召唤到内存来继续排，直到s1-1  s1-2 s1-3 s1-4都排完了，生成了s2-1  s2-2 s2-3  s2-4是肯定有序的 ；然后同理再排s1-5  s1-6  s1-7 s1-8 , s1-[9-12].......

这样s2-[(4(k-1)+1)-4k]   (k=1,2,.....1250)全部都是有序的

第３轮排序

把s2-1和s2-5召唤到内存，进行排序，其中一个排完了输出到s3-1，并把它组内的下个小伙伴召唤到内存，就这样排完了s2-[1-8]收获了s3-[1-8]，然后再排s2[9-16]得到s3-[9-16]，然后依此类推。。。

这样s8-[(8(k-1)+1)-8k]   (k=1,2,.....625)全部都是有序的

第４轮排序

想说同第三轮思路一致的，但是发现个问题625/8不是整数，约等于78组，先让78组先排，最后不满１组的也要在组内同理排序，可以认为自成一组（这个跟倒酒一个道理，900ml的酒水至少要用2个500ml的杯子装吧）。其实分多少组无所谓，只要保证组内有序就ok。

第５轮

.

.

.

排序结束

第１３轮之后妥妥的保证有序，每次都是对两个分片排序，最大内存大概用了20M+20M+20M（这个是给缓冲区用的）=60M吧。空间复杂度大概可以排完就删吧，看你怎么理解了，最小可以假装认为是每排完一个20M则输出一个20M，100G的辅助内存，最大可以认为是保存了所有临时结果，13*100G

二、先拆分在再合并

100G数据分成20M一份（本来想分成３０的，可惜数学不好），这样得到5000个分片（假装算对了）

5000个分片分别叫s0-1   s0-2   s0-3  s0-4 .....................s0-5000

第１轮排序

先把s0-1  s0-2召唤到内存进行排序，输出到外部分别为s1-1   s1-2

然后同理再把s0-3  s0-4为一组 s0-5  s0-6一组.......排出s1-3   s1-4    s1-5  s1-6.......

注意，排完之后第s1-1和s1-2，s1-3和s1-4，s1-5和s1-6.......组之间是无序的，但是组内是有序的

然后

从s１-[1-5000]中分别取0.01M的数据，这样需要50M内存，缓冲区设置为10M吧（这样好算），对这5000份0.01m的数据进行选择排序，排序结果放到缓冲区，缓冲区满就刷出保存到硬盘并清空缓冲，排序过程中如果其中属于任何一份的0.01m数据消耗完了要及时从该份拉取下一个0.01m，不然会有问题的，因为不仅要保证内存中的数据有序，还要保证整体（外部数据）也有序。

这里提到用选择排序，个人觉得比较容易理解，其中一个分片假设s1-99的第1个0.01M消耗完了，可以拉取s1-99的第2个0.01M存（替换）到第1个0.01M的位置。但效率么。。。应该和归并差不多

或者可以使用归并排序，同理在归并排序，排序过程中，其中有一个分片到结尾了，要及时的从内存中拉取该分片的下一个0.01M数据并存（替换）到该分片的第1个0.01M的位置，这样消耗的总内存一直不会增长。

排序结果

每次缓冲区刷出保存到硬盘都是追加到外部文件，排序结果就是一个有序的100G文件吧，当然也可以分成多份保存。

写了改，改了再写，反反复复，想写的无bug且通俗易懂还挺难的，欢迎评论！