一、外部排序：

指的是大文件的排序，待排序的记录存储在外存储器上，需要进行内外存交换。
外部存储设备：磁带，磁盘

二、外部排序的方法：

1. 文件分割成长度为l的子文件或段segment,在内存排好序后输出到外存，有序的文件叫归并段。
2. 归并段进行逐趟归并，合并成一个大文件

三、多路平衡归并的实现

1. k-路归并排序的时候利用大顶堆或小顶堆

四、置换-选择排序：

1. 在树形排序的基础上得来的，在整个排序的过程中，选择最小或最大关键字和输入输出交叉或平行进行。

五、最佳归并树：

1. 构造哈夫曼树
2. 若按最佳归并树的归并方案进行磁盘归并排序，需要在内存中建立一张载有归并段的长度和它在磁盘上的物理位置的索引表