外部排序问题

当数据量超过内存量，通过一般意义上的排序算法已经不能胜任排序工作了。我们需要借助于外存，保留我们排序的中间阶段。

处理过程

（1）按可用内存的大小，把外存上含有n个记录的文件分成若干个长度为L的子文件，把这些子文件依次读入内存，并利用有效的内部排序方法对它们进行排序，再将排序后得到的有序子文件重新写入外存。
（2）对这些有序子文件逐趟归并，使其逐渐由小到大，直至得到整个有序文件为止。（归并过程需要用到败者树或最小堆和一个内存缓冲区）。

外部排序.jpg

解题

分别排序：根据内存1G，数据10G，我们将10G数据切分成10份，通过内存调用磁盘的方式，每1G进行排序，排序结束后，我们会得到10个有序的数据数组。
归并：多路归并过程可以使用败者树或最小堆。为方便起见我还是用最小堆吧，原理是一样的。
内存中开辟一个大小为10的最小堆，和一个缓冲区（小于1G，不要太小）。
取10份排序好的数据的首位进入最小堆。则最小的数位于堆顶，移除堆顶元素并写入缓冲区，然后从移除元素的元素所属数组中的下一位进入最小堆，在次移除堆顶进入缓冲区...直到缓冲区满，缓冲区回写磁盘，清空缓冲区，再次将数据置入最小堆...
直到10份数据全部写完，然后将最小堆的元素按顺序回写磁盘即可。