Engineering a Cache-Oblivious Sorting Algorithm

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

In ACM Journal of Experimental Algorithmics, Special Issue of ALENEX 2004, volume 12(Article No. 2.2), 23 pages, 2007.

Abstract

This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by empirical methods a number of implementation issues and parameter choices for the cache-oblivious sorting algorithm Lazy Funnelsort, 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 are able to 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 © 2007 by the Association for Computer Machinery, Inc.

Online version

jea07.pdf (331 Kb)

DOI

10.1145/1227161.1227164

Links

BIBTEX entry

@article{jea07,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Kristoffer Vinther",
  doi = "10.1145/1227161.1227164",
  issn = "1084-6654",
  journal = "ACM Journal of Experimental Algorithmics, Special Issue of ALENEX 2004",
  number = "Article No. 2.2",
  pages = "23",
  title = "Engineering a Cache-Oblivious Sorting Algorithm",
  volume = "12",
  year = "2007"
}

Other versions