Engineering Cache-Oblivious Sorting Algorithms

Master's Thesis


Kristoffer Vinther

A 27-funnel with order 3 basic mergers, as seen from above


The thesis presented here is a slightly revised version of the original. The original is available at the Library of Computer Science and Mathematics. The changes from the original include mostly language and minor mathematical errors; no new benchmarks are included, nor have any changes to the algorithms or their implementation been made.

The XML versions are written in an extended subset of (read: based on) the proposed XHTML2 standard. They are still very incomplete.

The entire thesis [pdf]

Abstract [pdf]
Chapter 1 Introduction [pdf]
Chapter 2 Modern Processor and Memory Technology [pdf]
Chapter 3 Theory of I/O Efficiency [pdf]
Chapter 4 Cache-Oblivious Sorting Algorithms [pdf]
Chapter 5 Engineering the Algorithms [pdf]
Chapter 6 Experimental Results [pdf]
Chapter 7 Conclusion [pdf]
Appendix A Electronic Resources [pdf]
Appendix B Test Equipment [pdf]
Appendix C Supplementary Benchmarks [pdf]
Bibliography [pdf]
Index [pdf]


Slide presentation from the oral defense [pdf]. Sums up nicely the results and major contributions of the thesis.


All source is released here under the GNU General Public License.

If you're in the business of verifying results presented in other people's theses, or is just generally inquisitive, do feel free to download the source code[zip] the thesis results are based on or download the binaries used.

If, on the other hand, you're into some serious sorting, visit the funnelsort project page, where some sporadic development on the source is still ongoing.


You can browse through the raw benchmark results here. All charts are available in Appendix C [pdf].


Rolf Fagerberg () and Gerth Stølting Brodal ()



Last updated: April 13th, 2005.