Suffix Array Construction: Rank-Space Scatter (2D)

Source String

Auto-step interval 900 ms

Doubling State

Round

Prefix sorted

1 char

Distinct ranks

–

Comparator calls

SA = [ … ] — press Step

How it works

Same prefix-doubling algorithm as the 3D version, drawn a completely different way: instead of rows of letter-cubes re-sorting in a room, every suffix is plotted as a point in the actual 2D space the sort key lives in.

rank⁰[i] = code(s[i])                         (round 0: sort by 1 char)
key[i]   = ( rankᵏ[i], rankᵏ[i+k] )            (x = primary rank, y = secondary rank)
rankᵏ⁺¹  = dense rank of key, after sorting all i by key
k        = 2k   (doubles every round)

Each round's sort key is a pair of numbers — exactly an (x, y) coordinate. This view plots every suffix at that coordinate: its column is the rank it already has going into this round, its row is the rank of the suffix k positions ahead (or the bottom "end" row past the string). The white path snakes through the points in the order the sort actually produces — reading the path top-to-bottom is reading the new suffix array directly out of the scatter, no camera angle involved.

Step round — runs exactly one doubling round: builds each suffix's (rank, rank+k) key, sorts by it, and compresses ties into new dense ranks.
Auto — steps automatically at the chosen interval until the array is fully sorted.
Columns — one per distinct primary rank; points sharing a column still need the secondary rank (y) to be told apart — once every point sits alone, the array is sorted.

Real-world relevance: this construction (and its linear-time cousin, SA-IS) underlies full-text indexes used in genome aligners (e.g. BWA), the Burrows–Wheeler family, and grep-scale substring search over gigabyte corpora.

Sort path (new suffix array order) Bucket boundary (rank changes)

⚠ Couldn't load the engineSomething went wrong initializing the canvas. Reload the page.