问题描述:

外部排序针对的是大文件的排序，即内存容量有限的情况下，待排序文件不能一次性放入内存进行排序，需要在内存和外部存储器之间进行多次数据交换，以达到对整个文件进行排序的目的。

外部排序最常用的方法就是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排 序的子文件进行多路归并排序。

算法流程：

  1. 将大文件分成n个小文件

  2. 分别放入内存排序，得到n个有序文件

  3. 建立一个小顶堆

  4. 将每一部分文件的最小元素加入堆中，此时堆顶元素就是n个文件中的最小元素

  5. 将堆顶元素弹出，并将堆顶元素所在文件的下一个元素加入堆中

  6. 重复4和5直到所有文件读取结束

复杂度：

空间复杂度：小顶堆所占用空间$O(k)$

时间复杂度：$O（knlogk）$，$logk$为堆的高度，$kn$为添加到堆中的总结点数。