Q：为什么需要外部排序？
A：因为数据规模太大，光读入都会爆内存…
“需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序，在排序过程中需要多次进行内存和外存（磁盘）之间的交换。这种排序方法就称为外部排序。”
由于磁盘IO比内存IO慢得多（大概慢5个数量级），所以瓶颈完全在于前者，故为了方便时间开销主要考虑前者的次数
Merge sort外部排序通常采用归并排序法，分为两个阶段：一，形成初始归并段；二，多路归并
形成初始归并段：将待排文件根据内存大小合理切片，分别读入内存，执行内部排序，再写回外存，我们就得到了初始归并段
接下来要把所有的初始归并段归并成一个单一归并段（整个文件有序）。我们先假设采用二路归并。到了后期，每个归并段长度都相当于若干初始归并段长度之和，显然直接读入还是会爆内存，所以这里的二路归并与内排序的有点区别。为了避免爆内存，我们将内存划分成三部分：两个input buffer和一个output buffer。归并排序的好处这时就体现出来了，因为我们不需要知道整体的信息，每次只需要关心归并段的局部。若input buffer空了，就再把一部分归并段的record读入buffer。若output buffer满了，就把output buffer写入外存，清空。
设 n n n为record总数， m m m为初始归并段数
Q：为什么要用多路归并？
A：由上述讨论知，瓶颈在于磁盘IO次数。而归并的趟数越多，磁盘IO次数也越多。多路归并可以减少归并趟数（归并树高从
log
2
m
log_2m
log2m变成
log
k
m
log_km
logkm）。
考虑最朴素的k路归并
k路归并，如果每次为了确定最小的数，都比较k-1次，总时间复杂度为
n
(
k
−
1
)
log
k
m
n(k-1)log_k m
n(k−1)logkm即
O
(
n
k
log
m
)
O(nklog m)
O(nklogm)，这肯定GG，在
k
k
k比较大的时候，k路归并甚至得不偿失，那还玩个der。。。
显然不用这么暴力。
k个叶结点分别存放k个归并段在归并过程中当前参加比较的record，内部结点用来记忆左右子树中的“失败者”，而让胜利者往上继续进行比较，一直到根结点。假定比较两个数，大的为失败者，小的为胜利者，则根结点指向的数为最小数。
可见败者树的性质使得每次确定下一个最小的数（重构败者树）只需要
log
2
k
log_2k
log2k的时间，那么总时间复杂度就是
n
log
2
k
log
k
m
=
n
log
2
m
nlog_2klog_km=nlog_2m
nlog2klogkm=nlog2m即
O
(
n
log
m
)
O(nlog m)
O(nlogm)
为了减少归并趟数，从而减少外存IO次数，一方面可以从
k
k
k入手，另一方面可以从减小
m
m
m入手。如果我们能减少初始归并段的个数，也即生成更长的初始归并段，就好了
我们注意到，初始归并段长度都相同（除了最后一段），它依赖于内部排序时可用内存工
作区的大小
置换-选择排序（生成初始归并段）步骤：
假设初始待排序文件为输入文件FI，初始归并段文件为输出文件FO，内存缓冲区为WA，可容纳P个记录。FO，W初始为空，
则置换-选择如下：
- 从FI输入P个记录到缓冲区WA
- 从WA中选择出关键字最小的记录MIN
- 将MIN记录输出到FO中去
- 若FI不空，则从FI输入下一个记录到WA
- 从WA中所有比MIN关键字大的记录中选出最小关键字记录，作为新的MIN;(WA中比MIN关键字小的暂时不能选，即不能作为当前归并段的记录)
- 重复(3)~(5)，直到在WA中选不出新的MIN为止。得到一个初始归并段，输出归并段结束标志到FO中
- 重复(2)~(6)，直到WA为空，由此得到全部初始归并段。
注意，如此法得到的初始归并段长度可能就千奇百怪了
最佳归并树归并排序的执行过程可以用归并树来描述，并且我们可以定量研究外存IO次数
为了减少归并趟数，另一个入手角度是合理组织归并排序归并段的次序，即合理确定归并树的形状。显然k路归并的最优次序就是k叉Huffman树的形状（叶节点的权值就是初始归并段的长度）。
k叉Huffman树注意，很有可能要补0！
外存读写次数=2*WPL，乘2是因为读写各一次
