Suffix Array Construction: Prefix-Doubling Algorithm

Building a suffix array by sorting whole suffixes directly is quadratic-ish and slow; the classic O(n log n) trick sorts by doubling prefix lengths instead. Each round pairs every suffix's current rank with the rank of the suffix k positions ahead, sorts all n suffixes by that pair, and compresses the sorted order into fresh dense ranks — which doubles the length of prefix each suffix is correctly ordered by. This simulator renders every suffix of a chosen demo string as a row of character cubes in 3D, re-sorts and animates the rows into their new order on every round, and tracks the round count, the prefix length now correctly sorted, how many of the n ranks are already distinct, and the number of comparator calls the sort performed — stopping automatically once every suffix has a unique rank, which is exactly when the rows already show the final suffix array.