Engineering a cache-oblivious sorting algorithm

DOI10.1145/1227161.1227164MaRDI QIDQ3507783zbMATH OpenOpenAlexFDO

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

Publication date 20 June 2008

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1227161.1227164

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• On the limits of cache-obliviousness
• scientific article; zbMATH DE number 2011837
• Towards a theory of cache-efficient algorithms
• The Influence of Caches on the Performance of Sorting
• Automata, Languages and Programming

Cited in

(14)

• scientific article; zbMATH DE number 1670675 (Why is no real title available?)
• On the limits of cache-obliviousness
• Design and Engineering of External Memory Traversal Algorithms for General Graphs
• The Influence of Caches on the Performance of Sorting
• On the design of a high-performance, expandable, sorting engine
• BlockQuicksort: avoiding branch mispredictions in Quicksort
• Cache oblivious algorithms for computing the triplet distance between trees
• In-place parallel super scalar samplesort (\(\mathrm{IPS}^4\mathrm{o}\))
• Analysing cache effects in distribution sorting
• Efficient sorting using registers and caches
• Proximity MergeSort, optimal in-place sorting in the cache-oblivious model
• External-memory sorting with comparison errors
• Optimal cache-oblivious mesh layouts
• When are cache-oblivious algorithms cache adaptive? A case study of matrix multiplication and sorting

Describes a project that uses

Uses Software

• TPIE

This page was built for publication: Engineering a cache-oblivious sorting algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3507783)