而当待排序的文件比内存的可使用容量还大时,文件无法一次性放到内存中进行排序,需要借助于外部存储器(例如硬盘、U盘、光盘),这时就需要用到外部排序算法来解决。

外部排序算法由两个阶段构成:

  • 按照内存大小,将大文件分成若干长度为 l 的子文件(l 应小于内存的可使用容量),然后将各个子文件依次读入内存,使用适当的内部排序算法对其进行排序(排好序的子文件统称为“归并段”或者“顺段”),将排好序的归并段重新写入外存,为下一个子文件排序腾出内存空间;
  • 对得到的顺段进行合并,直至得到整个有序的文件为止。

最佳归并树

对于如何判断是否需要增加虚段,以及增加多少虚段的问题,有以下结论直接套用即可:

在一般情况下,对于 k–路平衡归并来说,若 (m-1)MOD(k-1)=0,则不需要增加虚段;否则需附加 k-(m-1)MOD(k-1)-1 个虚段。

  • m:归并段个数
  • MOD:求余函数,返回两数相除的余数

什么是外部排序算法