外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。
在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。尔后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。
1.读入100 MB的数据至内存中，用某种常规方式（如快速排序、堆排序、归并排序等方法）在内存中完成排序。
2.将排序完成的数据写入磁盘。
3.重复步骤1和2直到所有的数据都存入了不同的100 MB的块（临时文件）中。在这个例子中，有900 MB数据，单个临时文件大小为100 MB，所以会产生9个临时文件。
4.读入每个临时文件（顺串）的前10 MB（ 100 MB / (9块输入缓冲区 + 1块输出缓冲区)）的数据放入内存中的输入缓冲区，最后的10 MB作为输出缓冲区。（实践中，将输入缓冲适当调小，而适当增大输出缓冲区能获得更好的效果）
5.执行九路归并算法，将结果输出到输出缓冲区。一旦输出缓冲区满，将缓冲区中的数据写出至目标文件，清空缓冲区。一旦9个输入缓冲区中的一个变空，就从这个缓冲区关联的文件，读入下一个10M数据，除非这个文件已读完。
这是“外归并排序”能在主存外完成排序的关键步骤 -- 因为“归并算法”(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并)，每个大块不用完全载入主存。
性能分析
提高外排序效率应该主要着眼于减少外存信息的读写次数。
在一般情况下，对m个初始归并段进行k-路平衡归并时，归并的趟数
s=LOGk m （即以k为底以m为真数的对数）
可见，若减少m或者增加k可以减少归并的趟数，但是并不是k值的选择越大越好，如何选择k值是个综合考虑的问题。
多路平衡归并的实现
单纯增加k将导致增加内部归并排序的时间，若在进行k-路归并时利用“败者树”，则可使在k个记录中选出关键字最小的记录时仅需进行log2 k(以2为底以k为真数的对数，并且向上取整)。
"胜者树"：每个非终端结点均表示其左、右孩子结点中的"胜者"。
"败者树"：记下刚进行完的比赛的败者，而让胜者去参加更高一层的比赛。
为了防止在归并过程中某个归并段变空，可以在每个归并段中附加一个关键字为最大值的记录。当选出的"冠军"记录的关键字为最大值时，表明此次归并已完成。
2）、压缩输入输出文件和临时文件。
原文：http://blog.csdn.net/sxhlovehmm/article/details/44755103