Faster Suffix Sorting
Niklas Larsson · 1999
We propose a fast and memory efficient algorithm for lexicographically sorting the suffixes of a string, a problem that has important applications in data compression as well as string matching. Our algorithm eliminates much of the overhead of previous specialized approaches while maintaining their robustness for all kinds of input. For input size n, our algorithm operates in only two integer arrays of size n, and has worst case time complexity O(n log n). We demonstrate experimentally that our algorithm has favourable performance compared to other approaches, and argue that our algorithm is the prime choice for general suffix sorting.