置换选择排序

目的：将文件生成若干初始顺串（顺串越长越好，个数越少越好）。

实现：借助在内存中的堆来完成。

1. 将堆顶的值送出到输出缓冲区。
2. 设 $R$ 是输入缓冲区的下一条记录。

   1. 如果 $R$ 不小于刚输出的关键码值，就把 $R$ 放到根节点，然后向下筛选。

   2. 否则，说明 $R$ 不能位于当前顺串中。将当前堆的最后一个元素放到堆顶，把 $R$ 放在刚刚挪走的位置上。然后对堆顶向下筛选。

      堆的大小减一。

归并排序

最佳归并树

进行多路归并时，各初始顺串的长度不同，对外存扫描的次数会产生影响。

把所有初始顺串作为树的叶节点，顺串的长度（某一顺串包含磁盘块的块数）作为权重，建立一棵 K 叉哈夫曼树，就是 K 路归并的最佳归并树。

访外总次数即为两倍的外部路径长度和。

乘以 2 的原因：读入和写入。

赢者树 & 败者树

在做 k 路归并的时候，如果按照普通的比较方法，每次都需要做 $k-1$ 次比较，代价较大。

引入赢者树和败者树。

赢者树和败者树都是完全二叉树。

在败者树中，用父节点记录其左右子节点进行比赛的败者，而让获胜者去参加更高阶段的比赛。

比赛的过程

将新进入树的节点与其父节点进行比赛，把败者存放在父节点中，把胜者再与上一级的父节点进行比赛。