Radix sorting with no extra space

Gianni Franceschini, S. Muthukrishnan, Mihai Pǎtraşcu

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    It is well known that n integers in the range [1, nc] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1, U] can be sorted in O(n√log log n) time [5]. However, these algorithms use O(n) words of extra memory. Is this necessary? We present a simple, stable, integer sorting algorithm for words of size O(log n), which works in O(n) time and uses only O(1) words of extra memory on a RAM model. This is the integer sorting case most useful in practice. We extend this result with same bounds to the case when the keys are read-only, which is of theoretical interest. Another interesting question is the case of arbitrary c. Here we present a black-box transformation from any RAM sorting algorithm to a sorting algorithm which uses only O(1) extra space and has the same running time. This settles the complexity of in-place sorting in terms of the complexity of sorting.

    Original languageEnglish (US)
    Title of host publicationAlgorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
    PublisherSpringer Verlag
    Number of pages12
    ISBN (Print)9783540755197
    StatePublished - 2007
    Event15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, Israel
    Duration: Oct 8 2007Oct 10 2007

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume4698 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference15th Annual European Symposium on Algorithms, ESA 2007

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Radix sorting with no extra space'. Together they form a unique fingerprint.

    Cite this