Engineering Cache-Oblivious Sorting Algorithms

Master's Thesis by Kristoffer Vinther

Thesis

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]

Presentation

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

Source

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.

Benchmarks

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

Supervisors

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

Contact

E-mail:

Last updated: April 13th, 2005.