Funnelsort is a comparison-based sorting algorithm. It is similar to mergesort, but it is a cache-oblivious algorithm, designed for a setting where the number of elements to sort is too large to fit in a cache where operations are done. It was introduced by Matteo Frigo, Charles Leiserson, Harald Prokop, and Sridhar Ramachandran in 1999 in the context of the cache oblivious model.
Lazy funnelsort is a modification of the funnelsort, introduced by Gerth Stølting Brodal and Rolf Fagerberg in 2002. The modification is that when a merger is invoked, it does not have to fill each of its buffers. Instead, it lazily fills a buffer only when it is empty. This modification has the same asymptotic runtime and memory transfers as the original funnelsort, but has applications in cache-oblivious algorithms for problems in computational geometry in a method known as distribution sweeping.
- ^ Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science(FOCS 99), pp. 285-297. 1999. Extended abstract at IEEE, at Citeseer.
- ^Harald Prokop. Cache-Oblivious Algorithms. Masters thesis, MIT. 1999.
- ^Brodal, Gerth Stølting; Fagerberg, Rolf (25 June 2002). “Cache Oblivious Distribution Sweeping”. Automata, Languages and Programming. Lecture Notes in Computer Science. 2380. Springer. pp. 426–438. CiteSeerX 10.1.1.117.6837. doi:10.1007/3-540-45465-9_37. ISBN 978-3-540-43864-9. . See also the longer technical report.