转自http://hawstein.com/posts/9.4.html
k路归并可以参考leetcode题：http://blog.csdn.net/todorovchen/article/details/26366553
当面试官说到2GB文件的时候，他其实就是在暗示你， 他并不希望一次性把所有的数据都载入内存。这样子的话，我们要怎么做呢？ 我们每次就将部分数据载入内存就好了。
算法：
首先我们要了解，可以用的内存有多大？假设我们有X MB的内存可用。
- 我们将文件分为K份，其中X*K=2GB。每次取其中一份载入到内存中， 用O(nlog n)的算法排序，然后再保存到外部文件。
- 载入下一份并排序
- 当我们将K份小文件都排好序，合并它们。
上面的算法就是外排序，步骤3又称为N路归并。
使用外排序是由于数据太大了，无法一次全部加载到内存中，所以需要借助磁盘进行存储， 每次只从磁盘中加载一部分数据进入内存，进行排序。