【概述】
当对大文件进行排序时，由于文件中的记录很多，信息量庞大，无法将整个文件复制进内存中进行排序，因此需要将待排序记录存储在外存上，排序时再将记录一部分一部分的调入内存进行排序，在排序过程中需要多次进行内存和外存的交换
在 OS 中，是按块对磁盘信息进行读写的，由于磁盘读写的时间远超过内存运算时间，因此在外存排序过程中，时间代价主要考虑访问磁盘的次数，即 I/O 次数
【方法】
外部排序通常采用归并排序法，其包括两个相对独立的阶段：
- 根据内存缓冲区大小，将外存上的文件分为若干长度为 $l$ 的子文件，依次读入内存按照内部排序方法进行排序，排序完成后再写回内存，这些有序子文件称为归并段
- 对归并段逐趟进行归并，使归并段逐小到大，直到得到整个有序文件为止
在外部排序中实现两两归并时，由于不可能将两个有序段及归并结果段同时放入内存，因此要不停的将数据读出写入磁盘，一般情况下有：
显然，外存读写时间远大于内部排序时间与内部归并时间，因此应着力减少 I/O 次数
【优化方法】
一般来说，对于 $r$ 个初始归并段，做 $k$ 路平衡归并，归并树可用严格 $k$ 叉树(只有度为 $0$ 和度为 $k$ 的 $k$ 叉树)来表示
第一趟将 $r$ 个初始归并段归并为 $\left \lceil \frac{r}{k} \rceil \right.$ 个归并段，之后每趟归并将 $m$ 个归并段归并为 $\left \lceil \frac{m}{k} \rceil \right.$ 个归并段，直到形成一个大的归并段为止
而 由于树的高度满足：
因此，只要增大归并路数 $k$ 或减少初始归并段个数 $r$，都能减少归并趟数 $S$，进而减少读写磁盘次数，以提高外部排序速度
