振荡排序 (Oscillating Sort / Reversing Merge)

故事：钟摆的节拍

在磁带机时代，有一个令工程师头疼的问题：磁带倒带很慢。每次排序合并之后，都要把磁带倒回起始位置，才能进行下一趟。这段"倒带时间"完全是浪费。

1962年，Sobel 提出了一个聪明的想法：既然倒带这么贵，为什么不让磁带永远向前走？

他的方案：让奇数块的数据正向有序（升序），偶数块的数据反向有序（降序）。合并时，既能从左往右读升序块，也能从右往左读降序块——它们表现上都是有序的，可以直接参与合并！

这就是"振荡"（Oscillating）：数据像钟摆一样，一会儿向左，一会儿向右，但无论哪个方向都是有序的，都可以被高效地合并。

算法原理

振荡排序（Oscillating Sort）也称为 Reversing Merge，记载于 TAOCP 第3卷第5.4.4节。

核心思想

1. 内存分块排序（Replacement Selection 或简单 QuickSort）

   • 每次读取mem_size个元素到内存
   • 奇数块：排序为升序
   • 偶数块：排序为降序

2. 方向感知的合并

   • 升序 run：从左往右读
   • 降序 run：从右往左读（等价于升序）
   • 合并时统一按值从小到大输出

3. 振荡效果

   [1,3,5,7] [8,6,4,2] [2,4,6,9] [10,8,5,3] 升序↑ 降序↓ 升序↑ 降序↓ 合并后 → [1,2,2,3,4,5,6,7,8,9,...] （升序）

对比传统方法

传统两路合并： 生成所有升序 runs → 合并 → 倒带 → 合并 → 倒带 → ... 倒带开销不可忽视！ 振荡排序： 奇升偶降 → 合并 → 无需倒带，继续前进！ 适合直接存取的磁盘（随机读写不需要倒带）

算法流程（示例，n=16, mem_size=4）

初始输入: [9,3,7,1, 8,2,6,4, 5,0,3,1, 2,8,4,6] 分块排序（振荡）: 块0（升序）: [1,3,7,9] 块1（降序）: [8,6,4,2] ← 存储为[8,6,4,2]，从右读得[2,4,6,8] 块2（升序）: [0,1,3,5] 块3（降序）: [8,6,4,2] ← 存储为[8,6,4,2] 4路合并（方向感知）: 同时从4个块的"有序方向"取最小值 → [0,1,1,2,2,3,3,4,4,5,6,6,7,8,8,9]

多趟振荡合并

当初始 runs 太多（内存不够同时打开所有 runs）时，分多趟：

趟1: 合并相邻两个 runs → 新的（更大的）升序/降序交替 runs 趟2: 再次合并 → 更少的 runs ... 最终: 只剩一个 run（升序）

适用场景

• 磁盘直接存取：比磁带更灵活，可以随机读写任意位置
• 大数据集：内存只需容纳少量元素，绝大多数数据在磁盘
• 流式处理：数据一次读入，一次写出，无需多次遍历

复杂度

• 趟数: O(log(n/mem_size))
• 每趟 I/O: O(n)
• 内存: O(mem_size)，远小于 n
• 优势: 无倒带开销，磁盘/磁带顺序访问效率最高

振荡 vs 传统合并

现代意义

振荡排序的"方向交替"思想在现代排序中仍有回响：

• TimSort检测并利用降序段（直接翻转而非忽略）
• 外部排序优化利用磁盘顺序读写特性，避免随机寻址
• 流式排序在大数据管道中，方向感知合并减少缓冲区需求