一、外存、内存之间的交换
二、外部排序原理
每次从两个缓冲区中挑选最小的元素，放到输出缓冲区中，当输出缓冲区存储1KB之后，将其写回外存
第二趟归并
时间开销分析
时间开销主要在读写磁盘，如果可以减少归并次数，即减少了读写次数，这样可以提高效率
通过下面的败者树可以减少对比关键字次数
一次将四个磁盘块内容加入输入缓冲区进行内部排序，可以得到4个初始归并段，然后进行4路归并
三、败者树
派大星取代天净饭，并不需要重新进行比赛，只需要派大星与阿乐，程龙，孙悟空比较
如果新新加入的元素放在b1或b2，则只需要对比2次（看树的层次），若放在b3或b4，则只需要对比3次
四、置换-选择排序
可以先将14输出
接下来构造归并段2
上面演示，是一个一个元素进行移入
实际上，选出的元素会先加入输出缓冲区，等输出缓冲区满了之后，会将其一次性写入磁盘
对于初始待排序序列，也是先将其加入输入缓冲区，每一次会读入好几个，然后一个一个的将其加入内存工作区。
四、最佳归并树
先找权值最小的，先归并
添加几个长度为0的虚段