外部排序的原理
例子
使用归并排序，最少只需在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序。
使用归并排序是需要构造一个有序的子序列。将外存的每块的数据两两读取到缓冲区内即可进行对数据的操作。
对读入缓冲区的块执行内部排序（即使用并归排序使），使每块有序。
将修改好的内容依次放入输出缓冲区进行输出，写入磁盘
依次读取后边的内容执行上述操作。
最终结果如下：
得到八个初始的归并段。可以用这八个归并段经行归并排序。
第一趟归并：
将两个归并段中更小的块读入缓冲区中，选择其中使用并归排序选择最小的放入输出缓冲区，当输出缓冲区满后执行输出。
输出缓冲区的数据写入外存后缓冲区变空。继续比较。如果一个缓存的数据变空则需要立即用相应归并段的下一个块补上。
此后继续执行比较
重复上述步骤。
注：归并好的数据是保存在磁盘的另外的位置的，原先存储的地方已经被释放掉了。此处只是为了美观才写在原先位置的。
后表面的归并段使用上述类似的方法
第二趟归并：
类似于第一趟归并的方法。最后结果如下：
时间开销分析
读写磁盘时间
128次（3×32+32）【占外部外序很大一部分，假设每一次读写要10ms，则总共需要1.28s】。
文件总块数不能改变。但是可以改变归并趟数。归并趟数减小，则相应的时间开销也会减小。是优化的思路。
优化思路
多路归并
之前采用的二路归并。也可以使用四路归并。操作类似于二路归并。注意一个缓冲区空了以后要使用归并段的下一块进行填充指导最后一块被归并完。
但是也并不意味着k可以无限增大！
如何减少初始归并段？生成初始归并段的内存工作区则可以增加初始归并段的长度从而减少初始归并段的数量。从而r也就越小。
总结：
补充：多路平衡归并
若有收获，就点个赞吧
0 人点赞
