振荡排序 (Oscillating Sort / Reversing Merge)054钟摆算法解码振荡排序故事钟摆的节拍在磁带机时代有一个令工程师头疼的问题磁带倒带很慢。每次排序合并之后都要把磁带倒回起始位置才能进行下一趟。这段倒带时间完全是浪费。1962年Sobel 提出了一个聪明的想法既然倒带这么贵为什么不让磁带永远向前走他的方案让奇数块的数据正向有序升序偶数块的数据反向有序降序。合并时既能从左往右读升序块也能从右往左读降序块——它们表现上都是有序的可以直接参与合并这就是振荡Oscillating数据像钟摆一样一会儿向左一会儿向右但无论哪个方向都是有序的都可以被高效地合并。算法原理振荡排序Oscillating Sort也称为 Reversing Merge记载于 TAOCP 第3卷第5.4.4节。核心思想内存分块排序Replacement Selection 或简单 QuickSort每次读取mem_size个元素到内存奇数块排序为升序偶数块排序为降序方向感知的合并升序 run从左往右读降序 run从右往左读等价于升序合并时统一按值从小到大输出振荡效果[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 → 合并 → 倒带 → 合并 → 倒带 → ... 倒带开销不可忽视 振荡排序 奇升偶降 → 合并 → 无需倒带继续前进 适合直接存取的磁盘随机读写不需要倒带算法流程示例n16, mem_size4初始输入: [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 传统合并特性传统外部归并振荡排序run 方向全升序升降交替倒带需求需要不需要实现复杂度简单中等I/O 效率有倒带损耗高效适用存储磁带磁盘/直接存取现代意义振荡排序的方向交替思想在现代排序中仍有回响TimSort检测并利用降序段直接翻转而非忽略外部排序优化利用磁盘顺序读写特性避免随机寻址流式排序在大数据管道中方向感知合并减少缓冲区需求