数据结构实战

        与内部排序相对的是外部排序，它指的是在计算机外存中对数据进行排序工作。当然排序时可以将外存中的文件数完全读入内存，然后利用内部排序算法对其排序，排序完成后再写入外存。然而大多数情况下外存数据非常大，常常大于内存的大小，这时我们无法一次性将文件内容读入内存进行排序，所以我们就需要一种可以对外存文件内容排序的算法。

        对于大型的文件排序算法通常采用2路归并或多路归并算法，其思想是先将文件分块，重新写入文件系统。排序时再对这多个文件块进行2路归并或多路归并。例如在外存中有一个1GB大小的数文件需要进行排序，我们可以先将其按顺序读入，每读入100MB就将其写入一个新的块文件，于是一个1GB的文件就被分解成了10个100MB的块文件。然后再对这10个块文件分别两两读入进行归并排序，最后将多趟排序的结果保存起来。

        外部排序与内部排序有一些区别，但其核心思想还是利用内部排序对外存数据进行排序。具体实现过程不再给出，请读者做为课后题自己完成。