Funnelsort (Ofer Abarbanel online library)

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.[1][2]

Lazy funnelsort

Lazy funnelsort is a modification of the funnelsort, introduced by Gerth Stølting Brodal and Rolf Fagerberg in 2002.[3] 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.

References

  1. ^ 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.
  2. ^Harald Prokop. Cache-Oblivious Algorithms. Masters thesis, MIT. 1999.
  3. ^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.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library