Engineering a cache-oblivious sorting algorithm

Gerth Stølting Brodal, Rolf Fagerberg, Kristoffer Vinther

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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 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.
OriginalsprogEngelsk
TidsskriftACM Journal of Experimental Algorithmics
Vol/bind12
ISSN1084-6654
StatusUdgivet - 2007

Bibliografisk note

Paper id:: 2.2

Fingeraftryk Dyk ned i forskningsemnerne om 'Engineering a cache-oblivious sorting algorithm'. Sammen danner de et unikt fingeraftryk.

Citationsformater