SA-IS Algorithm

Purpose: Build a suffix array in $O(n)$ time using induced sorting. It is both the asymptotically optimal and, in practice, the fastest general-purpose suffix array construction.

Algorithm

1. Append a sentinel $ smaller than every character.
2. Classify each suffix as S-type (smaller than the suffix to its right) or L-type (larger). One right-to-left pass: type[i] = (s[i] < s[i+1]) || (s[i] == s[i+1] && type[i+1] == S).
3. Mark LMS positions — S-type positions whose left neighbour is L-type. The LMS substrings (from one LMS position up to and including the next) tile the string.
4. Induced sort from a set of correctly placed LMS suffixes:
   • bucket suffixes by first character;
   • place the LMS suffixes at the ends of their buckets;
   • left-to-right pass: for each placed suffix $i$, if $i-1$ is L-type, put it at the current head of its bucket;
   • right-to-left pass: for each placed suffix $i$, if $i-1$ is S-type, put it at the current tail of its bucket.
5. Use step 4 with LMS positions in arbitrary order to obtain the correct relative order of LMS substrings. Name them, forming a reduced string of length $\le n/2$.
6. If all names are distinct, the reduced suffix array is immediate; otherwise recurse on the reduced string.
7. Map the reduced suffix array back to true LMS positions and run the induced sort (step 4) one final time. That is the suffix array.

Complexity

• Time: $T(n)=T(n/2)+O(n)=O(n)$
• Space: $O(n)$ integers (plus $O(\sigma )$ bucket counters)

Why It Works

The two induced passes rely on a simple ordering fact: within one character bucket, all L-type suffixes precede all S-type suffixes. Given that, if suffix $i$ is already in its final position, suffix $i-1$‘s position relative to other suffixes starting with the same character is fully determined by whether it is L or S, and by the order of the suffixes that follow. The passes therefore induce the full order from a correctly sorted subset — and the LMS suffixes are a subset small enough (at most $n/2$) to make the recursion linear by the geometric series.

Comparison

Method	Time	Practical speed	Code length
Naive sort of suffixes	$O(n^2\log n)$	terrible	3 lines
Prefix doubling + sort	$O(n{\log }^{2}n)$	fine to $n\approx 10^5$	~20 lines
Prefix doubling + radix	$O(n\log n)$	good to $n\approx 10^6$	~35 lines
DC3 / skew	$O(n)$	good	~60 lines
SA-IS	$O(n)$	best	~90 lines

In a contest

$O(n\log n)$ prefix doubling with radix sort is almost always enough, and it is far less error-prone to write under time pressure. Keep SA-IS in your template library rather than in your head.

Variants / Use Cases

• Kasai — pair with SA-IS for the LCP array in $O(n)$
• Burrows-Wheeler transform and FM-index — SA-IS is the standard construction step
• Bioinformatics — genome indexing is the reason linear-time SA construction is a solved engineering problem
• Suffix automaton — a different linear structure; often easier to code and covers most contest use cases
• Farach’s algorithm — the linear-time suffix tree analogue that inspired induced sorting