Funnel Sort | Codeboy's Blog

形式陈述

Funnel Sort 是缓存无关模型中的比较排序。输入 $N$ 个固定大小记录，慢存与快存之间每次搬运 $B$ 个连续记录，快存容量为 $M$ ；程序本身不读取这两个参数。

它的目标 I/O 界是

O\!\left( \frac{N}{B}\left(1+ \log_{M/B}\frac{N}{B}\right)\right).

当 $N$ 明显大于 $M$ 时，通常简写为 $O((N/B)\log_{M/B}(N/B))$ 。式中的 1 保留了小输入至少一次扫描的成本。该界与外存排序下界同阶。比较次数仍是 $O(N\log N)$ ，两种成本必须分开报告。

一个 $k$ -merger 接收至多 $k$ 条已排序输入流，反复执行 next，按全局非降序输出记录。它不是把 $k$ 个流头简单放进一个二叉堆；那样每个输出会沿堆走 $\Theta(\log k)$ 个可能分散的节点，无法自动得到顺序块传输。

Funnel 把二路 merger 组织成递归网络，并在中间边上放置不同容量的缓冲。下层 merger 只在上游缓冲需要补充时才运行，一次填入一批连续记录。缓冲大小随所连接子漏斗的规模增长，使一棵能放入缓存的子漏斗在生产大量输出期间无需频繁重新装入。

正确性不变量很简单：每条内部边上的缓冲保持有序，每个 merger 只比较两个输入缓冲的当前首项。因此从根输出的下一项是所有尚未输出记录中的最小者。复杂度的难点不在这个次序证明，而在选择递归形状和缓冲容量。

当 $N$ 足够小时，使用内存内比较排序作为基例。否则把输入划分为约 $N^{1/3}$ 个大小约 $N^{2/3}$ 的连续子数组，递归排序每一段，再交给一个 $N^{1/3}$ -merger 合并。

指数 $1/3$ 与 $2/3$ 让 merger 能以其设计容量处理所有子流，同时把递归问题显著缩小。实现必须处理非完美幂：最后一段可以更短，空输入流在 merger 中视为已耗尽；这不改变渐近界。

直觉

Funnel Sort 用递归网络在许多未知缓存尺度上同时形成多路归并。靠近叶子的缓冲吸收细粒度输入，靠近根的较大缓冲成批供应全局最小前沿；当某个子漏斗恰能驻留缓存时，它可以连续生产大量输出，成本便按整块摊到记录上。

例子与边界

设有八条排序流，首项依次为

1,4,6,9,12,15,18,22.

底层四个二路 merger 先把相邻流的小批量前缀写入四个缓冲；中层两个 merger 再各自按需填充更大的输出缓冲；根只比较这两个中层缓冲的首项。根先输出 1，随后补充该路径上的空槽，而不会扫描其余七条流。

若含 1 的输入下一项为 20，根接下来看到的全局最小值是 4。此时其他支路已经把 4、6 等候选顺序放在靠近根的缓冲里；磁盘上的长尾并未因每个输出而随机访问。一个缓冲耗尽时才触发 refill，refill 产生一段而非一个记录。

这个例子说明批量填充的方向，却不以八条流证明渐近界。真正分析在某个递归子漏斗首次能装入 $M$ 时，把它随后产生的 $\Theta(M)$ 级输出所需块传输摊到每条记录。

固定实际 $M,B$ ，在递归 merger 网络中选择大小刚好低于缓存容量的子漏斗。ideal-cache 可以在其活跃期间保留控制状态和热缓冲；每次读写仍以整块进行。跨过一个这样的尺度，每条记录只参加常数次顺序缓冲搬运。

记录从叶流到根要跨越

O\!\left(1+\log_{M/B}(N/B)\right)

个有效尺度，每个尺度总代价 $O(N/B)$ I/O，得到排序界。经典证明通常要求 tall-cache，例如 $M=\Omega(B^2)$ ，以保证选中的子漏斗及其边界缓冲能同时容纳，并使短缓冲的块浪费为低阶项。

缓存替换按 ideal-cache 的最优策略分析。真实 LRU、组相联缓存和预取器可能改变常数；“cache-oblivious”表示代码不调参，不表示物理存储没有块或任意替换策略都保留同一证明。

记录若为可变长对象， $B$ 个记录一块的换算不再成立。比较器若访问外部大对象，比较本身也会产生未计入的 I/O。稳定性不是结构自动给出的性质；需要在键相等时以原始位置打破平局。

普通归并排序的二路扫描每一层都顺序，但仍有 $\Theta(\log N)$ 层。知道 $M,B$ 的多路外存 mergesort 可直接选 $M/B$ 路；Funnel Sort 用递归 merger 同时适配未知的多级缓存，代价是更复杂的缓冲调度与较大的常数。

推论与应用

该算法证明缓存无关设计也能达到比较外存排序的最优 I/O 量级，并可由同一代码适配多级缓存。它更适合作为递归布局与缓冲分析的范型；实际实现若更重视常数、SIMD 或显式设备参数，已知 $M,B$ 的多路归并往往更直接。

参考资料

Matteo Frigo, Charles E. Leiserson, Harald Prokop and Sridhar Ramachandran, Cache-Oblivious Algorithms, ACM Transactions on Algorithms, 2012.
Harald Prokop, Cache-Oblivious Algorithms, MIT Master's Thesis, 1999.
Jeffrey Scott Vitter, Algorithms and Data Structures for External Memory, Foundations and Trends in Theoretical Computer Science, 2008.