publication . Conference object . Article . Part of book or chapter of book . Contribution for newspaper or weekly magazine . 2004

Engineering a cache-oblivious sorting algorithm

Gerth Stølting Brodal; Fagerberg, R.; Vinther, K.;
Open Access
  • Published: 01 Jan 2004
  • Country: Denmark
Abstract
<p>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.</p><p>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-awar...
Subjects
ACM Computing Classification System: Hardware_MEMORYSTRUCTURESData_FILES
free text keywords: Theoretical Computer Science
Related Organizations
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue