Engineering a Cache-Oblivious Sorting Algorithm

Gerth Stølting Brodal, Rolf Fagerberg, and Kristoffer Vinther

In Proc. 6th Workshop on Algorithm Engineering and Experiments, pages 4-17, 2004.

Abstract

This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate a number of implementation issues and parameter choices for the cache-oblivious sorting algorithm Lazy Funnelsort by empirical methods, and compare the final algorithm with Quicksort, the established standard for comparison based sorting, as well as with recent cache-aware proposals.

The main result is a carefully implemented cache-oblivious sorting algorithm, which our experiments show can be faster than the best Quicksort implementation we can find, already for input sizes well within the limits of RAM. It is also at least as fast as the recent cache-aware implementations included in the test. On disk the difference is even more pronounced regarding Quicksort and the cache-aware algorithms, whereas the algorithm is slower than a careful implementation of multiway Mergesort such as TPIE.

Copyright notice

Copyright © 2004 by the Society for Industrial and Applied Mathematics.

Online version

alenex04.pdf (279 Kb)

DOI

www.siam.org/meetings/alenex04/abstacts/alenex04.pdf

Links

Slides

alenex04.pdf (205 Kb)

BIBTEX entry

@inproceedings{alenex04,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Kristoffer Vinther",
  booktitle = "Proc. 6th Workshop on Algorithm Engineering and Experiments",
  doi = "www.siam.org/meetings/alenex04/abstacts/alenex04.pdf",
  isbn = "0-89871-564-4",
  pages = "4-17",
  title = "Engineering a Cache-Oblivious Sorting Algorithm",
  year = "2004"
}