Lars Arge

RAM-Efficient External Memory Sorting

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Lars Arge
  • Mikkel Thorup, University of Copenhagen, Denmark

In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we initiate a study of algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation. For sorting the conventional wisdom is to use merging base algorithms in external memory but we describe how this leads to suboptimal RAM performance. However, by using a splitting based algorithm in combination with existing RAM sorting techniques we obtain a sorting algorithm that is both I/O and RAM model efficient. Furthermore, we design an I/O- and RAM-efficient priority queue. Finally, we prove a sorting lower bound that shows that in most cases our results are optimal both in terms of I/O and internal computation.

Original languageEnglish
JournalAlgorithmica
Volume73
Issue4
Pages (from-to)623-636
Number of pages14
ISSN0178-4617
DOIs
Publication statusPublished - 2015

    Research areas

  • External memory algorithms, I/O algorithms, Priority queue, RAM algorithms, Sorting

See relations at Aarhus University Citationformats

ID: 97979552