级联合并排序 (Cascade Merge Sort)
053级联合并排序：瀑布流的排序智慧
故事：瀑布流的智慧
想象一条山间瀑布：水从高处的宽大水潭开始，分成多股支流奔涌而下，每一级台阶都比上一级更窄，但最终所有水流在山脚汇聚成一条大河。
级联合并排序（Cascade Merge Sort）正是从这个意象中诞生的。
1961年，一群工程师在研究如何最高效地使用多条磁带时，发现了一个有趣现象：如果不是每次都"填满"所有磁带再合并，而是像瀑布一样逐级减少参与合并的磁带数，就能在一大趟内完成更多工作。
具体来说，设有4条磁带（A、B、C、D），一个"大趟"是这样的：
- A+B+C → D（3路合并，直到其中一条用完）
- 被用完的那条成为新输出，继续 2路合并
- 再被用完的成为新输出，最后 1路复制
这像极了瀑布的级联：每一级台阶的水流都比上一级少一股，但都在流向同一个目标。
算法原理
级联合并排序（Cascade Merge Sort）是 TAOCP 第3卷第5.4.3节的内容，由 Betz 和 Carter 于 1959 年提出。
核心策略
设有 T 条磁带，每个"大趟"包含 T-1 个"小趟"：
T=4 的一个大趟： 状态: 磁带A[runs:5] 磁带B[runs:4] 磁带C[runs:3] 磁带D[空] 小趟1: A+B+C → D（3路合并） 合并到 C 磁带用完时停止 新状态: A[2个run剩余] B[1个run剩余] C[空] D[3个merged runs] 小趟2: A+B+D → C（3路合并，但实际只有2路有数据） 合并到 B 磁带用完时停止 新状态: A[1个run] B[空] C[1个merged run] D[2个剩余] 小趟3: A+C+D → B（继续） ...直到只剩一条磁带有数据与 Polyphase 的比较
| 特性 | Polyphase | Cascade |
|---|---|---|
| 初始分布 | 斐波那契数 | 相对均匀 |
| 每趟策略 | T-1路合并 | 级联递减 |
| 实现复杂度 | 较复杂 | 相对简单 |
| 效率 | 理论最优 | 略低于最优 |
| 适用场景 | 精确控制runs数 | 简单多路合并 |
复杂度
- 趟数: O(log_{T-1}(n))
- T=3: 约 log₂(n) 趟
- T=4: 约 log₃(n) 趟
- 空间: O(n) 磁带空间
级联特点
- 渐进减少：每个大趟内，参与合并的磁带数从 T-1 逐步降到 1
- 磁带复用：用完的磁带立即成为下一级的输出，磁带利用率高
- 简单调度：不需要精确计算斐波那契分布，初始分布相对简单
实际应用
级联合并在早期商业数据库系统中广泛应用，特别是在 IBM 360/370 系列大型机的磁带排序程序中。其简洁的实现使得维护成本远低于 Polyphase。
在现代数据库系统中，外部排序（External Sort）仍然是处理超大数据集的核心技术，级联和多路合并的思想融入了许多现代实现中。
