In-place suffix sorting

G. Franceschini, S. Muthukrishnan

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


    Given string T = T[1,... ,n], the suffix sorting problem is to lexicographically sort the suffixes T[i,... ,n] for all i. This problem is central to the construction of suffix arrays and trees with many applications in string processing, computational biology and compression. A bottleneck in these applications is the amount of workspace needed to perform suffix sorting beyond the space needed to store the input as well as the output. In particular, emphasis is even on the constant c in the O(n) = cn space algorithms known for this problem, Currently the best previous result [5] takes O (nv + n log n) time and O (n/ √v) extra space, for any v ∈6 [1, √n] for strings from a general alphabet. We improve this and present the first known in-place suffix sorting algorithm. Our algorithm takes O (n log n) time using O(1) workspace and is optimal in the worst case for the general alphabet.

    Original languageEnglish (US)
    Title of host publicationAutomata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings
    PublisherSpringer Verlag
    Number of pages13
    ISBN (Print)3540734198, 9783540734192
    StatePublished - 2007
    Event34th International Colloquium on Automata, Languages and Programming, ICALP 2007 - Wroclaw, Poland
    Duration: Jul 9 2007Jul 13 2007

    Publication series

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


    Conference34th International Colloquium on Automata, Languages and Programming, ICALP 2007

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'In-place suffix sorting'. Together they form a unique fingerprint.

    Cite this