外部排序
1. 外存、内存之间的数据结构
特点：外存大，存储数据多；内存小，存储数据少。 规定：外存的数据只有读到内存之后才能进行修改，修改之后还要写回到外存（可以写回原来不同的位置）。
2. 外部排序原理
简单来说，因为外存数据又多又杂，就要一点一点读入到内存中排序，然后再写回外存。 逻辑：外存–>读出数据–>内存–>在内存有序排列数据（比如一个块三个数据 632 排成 236）–>写回外存。
2.1 构造初始归并段
因为内存腾出了两个存放数据块的位置（输入缓冲区）和写出数据的位置（输出缓冲区），2–>1，二合一就是二路归并。
从外存读入两个数据块放入内存的输入缓冲区内，然后就可以对这两个数据块进行归并排序了。
得到两个有序数列。
将这两个有序数列写回外存，这样就构成了一个有序的归并段。
经过 16 次读和 16 次写，外存就变成了左边的 8 个归并段。
2.2 第一趟归并
接下来就需要我们把归并段们继续归并排序：
- 将两个归并段中小的数据块读入内存
- 在内存中进行归并排序
- 将排序好的数据写回外存
注意：写回的位置是另外一片，不是原来的存放未排序数据的位置。
出现一整个缓冲区空白的情况，就继续读入一个数据块，然后继续进行归并排序：
第一趟归并结束后，就成功得到了四个大的归并段：
2.3 第二趟归并
和之前一样，挑出两个归并段中最小的一组，继续进行合并：
第二趟合并后，就得到了两个更大的归并段：
2.4 第三趟归并
最后，把这两个更大的归并段进行合并：
最终就得到了有序的数据：
3. 时间开销分析
- 读写外存的时间：就是构造初始归并段的时间
- 内部排序所需时间：就是排序花费的时间。
- 内部归并所需时间：就是几次归并花费的时间。
4. 优化
我们先对读写外存的这部分时间进行优化。
4.1 多路归并
我们可以在内存多申请几个输入缓冲区，实现多路归并，一次读入两个数据段和一次读入四个数据段，当然是后者 I/O 次数更小，还可以减少归并的趟数。
假设：第一趟归并用 4 路归并
第一次归并后就得到两个归并段，只需要再一趟就可以完全有序：
4.2 减少初始归并段数量
比如之前的我们的初始归并段是 8 个，现在减少为 4 个：
4–>2–>1，得到初始归并段后再归并两次就可以完全有序了
外存的总数据块数不变，初始归并段越长，初始归并段越少。
5. 小结
重点在平衡这两个字上：
败者树
1. 多路平衡归并带来的问题
多路平衡归并：一个数要和很多个数都要比一次，才能找到最小的那个数字，就很浪费时间。
2. 败者树的构造
就是两个人战斗，失败的留下，胜利的上去，继续和另一组胜利的人继续比，最终选出一个冠军。
这个时候冠军跑路了：
由派大星顶替它原来的位置
那么难道我们还要重新比 7 次么？！
答案是不需要，右侧的根本没被派大星影响，右侧胜利的依旧是孙悟空； 而派大星需要代替天津饭，先和阿乐比，赢了再和程龙比，赢了再和孙悟空比； 只需要比对三次就可以了
3. 败者树的使用
同样的规则，我们就可以搬到归并段上使用。
画出败者树：
每个归并段都排除自己最小的一个数字参赛：
- 27>12，27 留，12 上；1<17，17 留，1 上；2<9，9 留，2 上；11>4，11 留，4 上；
- 12>1，12 留，1 上；2<4，4 留，2 上
- 1<2，2 留，1 上；
- 上一次的冠军是 1，来自归并段 3，他就可以先走了
- 继续用归并段 3 内的数字接力，6 出来沿着 1 的比赛路径进行比拼
- 6<17，17 留，6 上，所以结点是 6 所在的归并段 3；
- 12>6，12 留，6 上，所以结点是 6 所在的归并段 3；
最终回合：6>2，6 留，2 上，所以结点是 2 所在的归并段 5；
这样就找出了最小的一个数
注意：结点中记录的是来自的归并段，而不是真实数字
所以再需要接着比赛选出最小的冠军，就只需要踩着前人的脚印，继续向上比拼。比如：
4. 败者树的实现思路
5. 小结
置换 - 选择排序
1. 土办法构造初始归并段
纯一块一块构造。
2. 置换 - 选择排序
- 工作区：只能放三个记录
- MINIMAX：刚刚写出的数据的值
- 规定：同一归并段，只能写出比 MINIMAX 大的数字
注意：这里的输出缓冲区省略了，但不代表没有
选择工作区内最小的但比 4 大的数字写出：
按照这个规律一直写出： 这里我们发现最小的一个数字是 10<13，而我们只能写出比 13 大的，所以就放着先不要动
当工作区内的数字都比 MINIMAX 小，不可以写出的时候：
我们就需要开一个新的归并段，经过写出最后是这样：
最后就得到了三个不定长的归并段：
注意：是有输出缓冲区存在的，只不过我们省略了而已
3. 小结
最佳归并树
1. 归并树的神秘性质
归并过程中的磁盘读写次数=归并树的 WPL*2 也就是最佳归并树是哈夫曼的形式
2. 构造最佳归并树
2.1 2 路
2.2 多路归并
如果减少一个归并段，那么单纯地按照哈夫曼树的逻辑处理得到的就不是最佳归并树了：
我们需要添加一个结点 0，然后再按照正常的步骤继续进行：
3. 添加虚段的数量
情景：类似于上面缺少一个归并段的时候，我们需要添加几个结点 0？ 结论：图片最后两行（代入例子更好理解）
4. 小结
