バケットソート
先頭の文字でソートする
一度に Suffix をソートするのは大変です． そこで先頭の文字に着目し，まずは先頭の文字についてソートしてみます．
| No. | 開始位置 | Suffix |
|---|---|---|
| 0 | 0 | abracadabra$ |
| 1 | 1 | bracadabra$ |
| 2 | 2 | racadabra$ |
| 3 | 3 | acadabra$ |
| 4 | 4 | cadabra$ |
| 5 | 5 | adabra$ |
| 6 | 6 | dabra$ |
| 7 | 7 | abra$ |
| 8 | 8 | bra$ |
| 9 | 9 | ra$ |
| 10 | 10 | a$ |
| 11 | 11 | $ |
すると，次の表で色分けしたように，先頭の文字が同じ Suffix のグループができます． このグループをバケットと呼ぶことにしましょう．
| No. | 開始位置 | Suffix |
|---|---|---|
| 0 | 11 | $ |
| 1 | 0 | abracadabra$ |
| 2 | 3 | acadabra$ |
| 3 | 7 | abra$ |
| 4 | 5 | adabra$ |
| 5 | 10 | a$ |
| 6 | 1 | bracadabra$ |
| 7 | 8 | bra$ |
| 8 | 4 | cadabra$ |
| 9 | 6 | dabra$ |
| 10 | 2 | racadabra$ |
| 11 | 9 | ra$ |
ソートを進めていくとバケット内での順番は変わる可能性がありますが， バケットの外に出ていってしまうことはなく，各バケット独立にソートを行うことができます． 各グループのサイズは元の配列より小さくなることが期待できるので，比較的簡単にソートできるはずです．
バケットソート
各 Suffix がバケット内のどこに入るかを知るのは大変ですが， どのバケットに入るかなら先頭の文字を見ればすぐにわかります． そして，各バケットの範囲は，文字毎の出現回数をカウントしておくことで簡単に知ることができます，
例えば「abracadabra$」では「$」が1回，「a」が5回，「b」が2回，「c」が1回，「d」が1回，「r」が2回出現しています． このことから各バケットの位置は次のようになることがソートをしなくてもわかります，
| No. | 開始位置 | Suffix | バケット先頭位置 |
|---|---|---|---|
| 0 | 11 | ←$の先頭=0 | |
| 1 | 0 | ←aの先頭=1 | |
| 2 | 3 | ||
| 3 | 7 | ||
| 4 | 5 | ||
| 5 | 10 | ||
| 6 | 1 | ←bの先頭=1+5=6 | |
| 7 | 8 | ||
| 8 | 4 | ←cの先頭=1+5+2=8 | |
| 9 | 6 | ←dの先頭=1+5+2+1=9 | |
| 10 | 2 | ←rの先頭=1+5+2+1+1=10 | |
| 11 | 9 |
あとは Suffix を該当するバケットの空いているところに入れていけば，先頭の文字に関するソートが完了します． 出現回数のカウントも，Suffix をバケットに入れる処理も と 普通のソートより速くソートすることができます．
問題点
しかし，「各バケット内のソートをどうするか」という問題が以前残ります． バケットソートを再帰的に適用することにより高速化可能ですが， 元の文字列に繰り返しが多いと再帰する回数が多くなってしまいあまり効率的ではありません． そのため，結局はマージソートやクイックソートなどの汎用ソートに頼ってしまうことになり， あまり速度が上がりません．