Funnel Sort

形式陈述 ​

输入、模型与保证 ​

Funnel Sort 在缓存无关模型理路缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。中完成比较排序理路比较排序Comparison sorting仅通过元素两两比较确定排列次序的排序模型。：输入为连续存放的 $N$ 个定长记录，输出保持全部记录并按键非降序排列。空输入和单项直接返回；程序的基例阈值是固定常数，不读取块大小 $B$ 或缓存容量 $M$。

在全相联、最优替换的理想缓存中，若 $M=\mathrm{\Omega }(B^2)$ 且内存至少容纳固定数量的块，对 $N\ge 1$ 有

次缓存缺失，比较工作为 $O(N\log (N+1))$。在这个 tall-cache 范围内，它与比较排序 I/O 下界理路外存排序 I/O 下界external-memory sorting lower bound · I/O sorting lower bound在原子记录的两层 I/O 模型中，排序需要与多路归并上界匹配的块传输次数。同阶，也等价于截断小输入对数后的外排表达式。开头的常数覆盖不足一块的非空输入。

带批量接口的 k-merger ​

一个 $k$-merger 保存合并状态；一次调用输出接下来的 $k^3$ 项，输入提前耗尽时只输出剩余有效项并报告结束。已排序输入通过 FIFO 缓冲提供。常数 $k\le 3$ 直接比较各个流头；一般 $k$ 则递归构造较小 merger。

先看每层平方根都与递归批量兼容的标准写法，例如 $k=2^{2^j}$（$j\ge 0$，$k=2$ 为常数基例），而不只要求最外层 $k$ 是平方数：$\sqrt{k}$ 个左 merger 各合并 $\sqrt{k}$ 条输入，每次产生 $k^{3/2}$ 项，写入容量为 $2k^{3/2}$ 的中间循环队列；一个右 $\sqrt{k}$-merger 再合并这些队列。右 merger 每次执行前，先给少于 $k^{3/2}$ 项且尚未耗尽的中间队列调用一次对应左 merger。填充后队列至少有一个右调用所需的最大消耗量，又不会超过容量；随后调用右 merger 输出 $k^{3/2}$ 项。重复 $k^{3/2}$ 次便输出 $k^3$ 项。

一般整数扇入，包括 $25$ 这类仅最外层为平方数的情形，采用下面统一的带保护版本：它为递归预取留下空间，不能只把所有平方根独立取整。一个保守实现取 $q=\lfloor \sqrt{k}\rfloor$ 个组，每组至多 $s=\lceil k/q\rceil$ 条流，左侧用 $s$-merger，右侧用 $q$-merger。令 $C_q$ 是右 merger 全部内部缓冲及尾批次最多能保存的记录数，在构造时即可计算。一次右调用输出至多 $q^3$ 项，按记录守恒，从任一输入读取的项数至多为 $T=q^3+C_q$。

因此每条中间队列预留 $T+s^3$ 容量；调用右 merger 前，反复调用对应左 merger，直到该队列至少有 $T$ 项或左输入耗尽。一次补充至多增加 $s^3$ 项，所以不会溢出。最后一个右批次若超出本次 $k^3$ 输出配额，多出的有效项保留供下次调用，至多 $q^3-1$ 项；空输入使用耗尽标志处理。因为 $C_q=O(q^2)$，这些前瞻空间仍只给每条队列增加 $O(k)$ 项，整体空间保持 $O(k^2)$。所有容量都只依赖扇入，不读取 $M,B$。

正确性按网络递归：左 merger 产生各自输入并集的有序前缀，中间 FIFO 保持这些前缀的次序，右 merger 再取各个前沿中的最小项。补充规则保证一个尚有更小项的分支不会因缓冲暂空而被误当成耗尽。因此每次输出恰为全体剩余输入的最小项，且每条记录恰输出一次。

排序递归 ​

对超出固定基例的 $N$，取 $k=\lceil N^{1/3}\rceil$，把输入分成 $k$ 段，各段长度至多 $\lceil N/k\rceil$，先递归排序，再用一个 $k$-merger 合并。因 $k^3\ge N$，一次批量调用足以输出全部记录；最后一段较短及空段按同一耗尽规则处理。