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)-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 中视为已耗尽；这不改变渐近界。

八条短流如何穿过漏斗

设有八条排序流，首项依次为 [ 1,4,6,9,12,15,18,22. ] 底层四个二路 merger 先把相邻流的小批量前缀写入四个缓冲；中层两个 merger 再各自按需填充更大的输出缓冲；根只比较这两个中层缓冲的首项。根先输出 1，随后补充该路径上的空槽，而不会扫描其余七条流。

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

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

I/O 分析的分层尺度

固定实际 (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 同时适配未知的多级缓存，代价是更复杂的缓冲调度与较大的常数。

参考资料

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.

要解决的不是比较次数 ​

k-merger 的接口 ​

排序递归 ​

八条短流如何穿过漏斗 ​

I/O 分析的分层尺度 ​