シェアソートでは、2n+1(nは前回出てきた複雑な式)の回数ソートしたときを終了とし、
途中でソートが終了してもそれを検知しません。
一見無駄じゃないか、と思うので調べてみました。
10000個(100×100)のすべてユニークなランダムにした要素をソートします。
このとき、理論上では15回ソートが必要です。
実際にやってみた結果…なんと、20回中19回が15回目のソートで完了し、
残りの1回は13回目のソートで完了、という結果になりました。
よって、途中でソート終了を検知するのはあまり効果がないと結論付けられそうです。
マクロを動かした人なら気づくかもしれませんが、実感とずれてないでしょうか。
シェアソートマクロの場合は11×11なので9回ソートが必要なのですが、
そんなにソートしなくても終了していたという気がしませんか。
現にライトニングトークでは6回のソートで終了しています。
理由は、最初に行ったソートです。
古典的シェアソートは横ソートからスタートしますが、縦ソートからスタートしている人が多いはずです。
最初に縦ソートをすると、その縦ソートが無駄になる場合もあるので、
完了までに必要な最大ソート回数が1回増えます。
冒頭で出た10000個のソートを、最初に縦ソートを行うように変更して試行します。
20回中、10回が8回目のソートで終了し、10回が10回目のソートで終了しました。
最初に横ソートを行うより、ずいぶんと速いです。
なぜこんな差が出るのか、シェアソートマクロで見てみます。
このデータに対して、まず縦ソートを行います。
このようなソート結果になりました。
次は横ソートを見てみます。
横ソートを行いました。
この段階ではまだ違いが分かりにくいので、さらに縦ソートを行ってみます。
最初に縦ソートを行った場合と比較してみましょう。
最初に縦ソートを行った場合はずいぶんと平らなのに対し、
横ソートを行った場合は四隅に寄るような形になっています。
青色の高さに注目すると、縦ソート版は3なのに対し、横ソート版は5です。
前回のエントリーで、高さを低くしていく必要がある、と書きました。
ですから、最初から高さが低い方がソートは速く進むのです。
ランダムに並んでいる場合は縦ソートできれいに低くなるのですが、
横ソートで大きい要素や小さい要素を端に集めてしまうと、高さが高くなってしまいます。
最大ソート回数が1回多くなっても、縦ソートを先に行うべきだと思います。