In computer science, funnel sort is a comparison based external sorting algorithm. Funnel sort was introduced in 1999 in the context of the cache oblivious model. In this model the number of memory transfers needed to sort ${\displaystyle N}$ keys on a machine with a cache of size ${\displaystyle Z}$ and cache lines of length ${\displaystyle L}$ is${\displaystyle O(1+N/L(1+\log _{Z}(N))}$ under the assumption that ${\displaystyle Z=\Omega (L^{2})}$. This has been proved to be asymptotically optimal for comparison based algorithms. For comparison, classic 2-way Mergesort incurs ${\displaystyle O(N/L\log(N/Z))}$ cache misses, which is a factor of ${\displaystyle \Theta (\log(Z))}$ worse than optimal.

Funnelsort has optimal work complexity of ${\displaystyle \Theta (N\log N)}$.

• MATTEO FRIGO, CHARLES E. LEISERSON, HARALD PROKOP, AND SHIDHAR RAMACHANDRAN. "Cache-oblivious algorithms". Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York, 1999
• AGGARWAL, A., AND VITTER, J. S. "The input/output complexity of sorting and related problems". Communications of the ACM 31, 9 (Sept. 1988), 1116–1127.

• http://kristoffer.vinther.name/projects/funnelsort/
  • http://kristoffer.vinther.name/academia/thesis/
• http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-fourteen/