T41 外部排序 减小归并趟数的方法

若初始归并段数量为 $N$，归并路数为 $k$

• 增加每个初始归并段的长度：通过增加内存缓冲区的大小，可以使每个初始归并段包含更多的数据，从而减少归并的次数。
• 使用多路归并, 归并趟数 = $\lceil {\log }_{k}N\rceil$
  • 最少需要分配 3 个缓冲区 (2 个输入 + 1 个输出), 每次归并至少需要 IO 2 次 (读出 + 写入)
  • 平衡归并: 多路归并时，每次都将相同数量的归并段合并，以保持归并树平衡 (尽可能地减少树的深度，保证归并趟数最小)
• 使用败者树进行归并：败者树可以高效地找到当前最小的元素(所在的归并段号)，从而减少比较次数，提高归并效率。
  • 一种特殊的完全二叉树, 高效地从 $k$ 个输入缓冲区中选出最小的元素 (复杂度 $O(\log k)$)
  • 将 $k$ 个输入序列的第一个元素两两比较，并将败者存储在父节点中，逐级向上，直到根节点
  • 胜者直接存储在根节点处（或直接通过根节点的比较得出）

关于补充虚段

• 虚段：补全叶节点使它成为满 $k$ 叉树
  • 度为 $k$ 的结点：$\frac{n_0-1}{k-1}$, 这个数字需要是一个整数
  • 构造 (多路) 哈夫曼树时，虚段视为权值为 0的结点参与计算