多路归并

在外部归并排序中，若每次只归并两个归并段，归并趟数可能较多。把二路归并推广为 $k$ 路归并，就可以一次合并最多 $k$ 个归并段。

若有 $r$ 个初始归并段，采用 $k$ 路归并，归并趟数为：

$$
S=\lceil \log_k r\rceil
$$

$k$ 越大，归并趟数通常越少，磁盘 I/O 次数也随之减少。

多路归并的代价

多路归并不是只有好处。

影响 原因
输入缓冲区增多 $k$ 路归并至少需要 $k$ 个输入缓冲区和一个输出缓冲区
选最小记录的比较次数增加 若朴素扫描 $k$ 个归并段首记录，每输出一个记录最多比较 $k-1$ 次

所以多路归并的矛盾是：

$$
k\uparrow\Rightarrow S\downarrow,\quad \text{磁盘 I/O 减少}
$$

但同时：

$$
k\uparrow\Rightarrow \text{选最小记录的内部比较代价增加}
$$

多路平衡归并

$k$ 路平衡归并满足两个条件：

  1. 每次最多把 $k$ 个归并段合并为一个新归并段。
  2. 若某一趟有 $m$ 个归并段参与归并，则这一趟后得到：

$$
\lceil m/k\rceil
$$

个新归并段。

不要把所有 $k$ 路归并都叫作 $k$ 路平衡归并

例如有 $8$ 个归并段，若做 $4$ 路平衡归并，一趟后应得到 $\lceil8/4\rceil=2$ 个新归并段。若人为分成 $4,2,2$ 三组，一趟后得到 $3$ 个新归并段，这不是 $4$ 路平衡归并。

# 败者树

败者树用于解决多路归并中“反复从 $k$ 个归并段首记录里选最小者”的问题。

败者树可以看作一棵完全二叉树：

  • $k$ 个叶结点对应 $k$ 个归并段当前参加比较的记录；
  • 除根结点外，其他内部结点记录本场比较中的败者来自哪个归并段；
  • 根结点记录全局胜者来自哪个归并段；
  • 胜者对应的叶结点就是当前所有归并段首记录中的最小者。

比较次数

第一次建立败者树时，所有叶结点都要参加比较。对于 $k$ 路归并：

$$
\text{建树比较次数}=k-1
$$

之后每输出一个最小记录，只需要让该归并段的新首记录沿原来的路径向上重新比赛，比较次数约为树高：

$$
\lceil \log_2 k\rceil
$$

这比每次朴素扫描 $k$ 个归并段的 $k-1$ 次比较少。

在归并中的使用

每次输出一个记录后：

  1. 记下冠军来自哪个归并段。
  2. 从该归并段取下一个记录，替换原冠军叶结点。
  3. 只沿该叶结点到根的路径重新比较。
  4. 新冠军就是下一次应输出的最小记录。

若某个归并段已经空，可把该叶结点的值视为 $+\infty$，这样它不会再成为冠军。

小结

考点 记法
多路归并作用 减少归并趟数，从而减少磁盘 I/O
多路归并代价 需要更多输入缓冲区，朴素选择最小者比较次数多
朴素选择 每输出一个记录最多比较 $k-1$ 次
败者树建树 $k-1$ 次比较
败者树调整 每输出一个记录约 $\lceil\log_2 k\rceil$ 次比较
败者树结点含义 非叶结点记败者，冠军继续上升