User:Gwern/Funnel sort

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 $N$ keys on a machine with a cache of size $Z$ and cache lines of length $L$ is$O(1+N/L(1+\log _{Z}(N))$ under the assumption that $Z=\Omega (L^{2})$. This has been proved to be asymptotically optimal for comparison based algorithms. For comparison, classic 2-way Mergesort incurs $O(N/L\log(N/Z))$ cache misses, which is a factor of $\Theta (\log(Z))$ worse than optimal.

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

References

• 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.

External links

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