Efficient Sorting Suffixes of Big Alphabets

An algorithm SACA-m is proposed to sort all suffixes of a read-only input string of n characters with alphabet size n
^O(1)
in O(n) time and O(n
^1/2
) workspace. It can be applied to sort suffixes of a general alphabet in O(n log n) time and O(n
^1/2
) workspace. This algorithm can be revised to a succinct variant SACA-1 to reuse the space of suffix array for O(1) workspace while keeping O(n) time. The time and space performance of both algorithms are evaluated by experiments on realistic and artificial datasets. These new results give the best time and space complexities for sorting suffixes of big alphabets.