多次元シェアソートの行きつく先を見てみましょう。
要素が増えたとき、1辺の長さを出来るだけ短くしたまま
次元数だけをどんどん増やしてソートを行う事を考えてみます。
最も短い1辺の長さは2です。
256個の要素があったら、1辺が2の八次元立方体を作ってソートします。
また、最後に逆にするのは面倒なので、
ソートする要素の選び方を工夫して
配列は正しい順に並べたままソートをする方法を考えます。
まずは、要素が8個、つまり一辺2の三次元立方体で考えます。
以下の図ができます。
そして、横ソート、縦ソート、段ソートのペアを抽出してみます。
横ソート [1, 2] [3, 4] [5, 6] [7, 8]
縦ソート [1, 4] [2, 3] [5, 8] [6, 7]
段ソート [1, 8] [2, 7] [3, 6] [4, 5]
さらにこれを図示します。
意外に単純な図が出来上がりました。
これなら、棟ソート(四次元方向ソート)やその上も簡単に作れるでしょう。
さて、要素が4つの場合は「横ソート→縦ソート→横ソート」の方法で完了しました。
ではこの要素が8個の場合は何所に段ソートを入れればいいでしょうか。
実は、段ソートを行っていい条件として
縦ソート、横ソート共に完了する必要があります。
それ以前に段ソートを実行しても、ある程度は揃うけど完璧ではないのです。
つまり、三次元シェアソートは以下のようにソートをします。
「横ソート→縦ソート→横ソート→段ソート→
横ソート→縦ソート→横ソート」
まるで二進数のビットが立っていく様子に似ています。
では、x個の要素(x=2^n)があったときの比較回数を求めてみましょう。
まず、ソート1回ではx/2回の比較が行われます。
そして、ソート回数は(x-1)回行われます。
よって、完了まで必要なソート回数は(x/2)(x-1)です！
あれ…ランダウの記号を用いるとこれは…O(n^2)なのでは？？
ということで、これ以上進んでも深みにはまるだけっぽいので
シェアソートはこれで終わりにしたいと思います。