下に黄色で示すのは、各要素がソート後にあるべき位置から
どれだけ離れているかの分布。
動きの遅い要素(亀)が発生せずに収束して行くのが判る。
自分には、比重の異なる粒子を混ぜたバケツを適度に揺すりながら
成層させる過程が連想される。
さて、この場合に櫛の間隔(GAP)の縮減率1.3であるが、
距離の平均(AVE)より小さくならない範囲で
速やかに減らして行くのがよさそうだが…。
縮減率1.2では控えめすぎる。
縮減率1.5では早過ぎて最後に亀が発生してしまう…これでは台無しである。
縮減率1.4の辺りが境目とすると、
やはり縮減率1.3は妥当と言えそうだ。
ソート対象の要素数:n / ギャップの縮減率:a / ギャップが１になるまでのステップ数:s とした場合
１ステップの比較交換は n - n / a^t 回 (ただし t = 1,2,3...)なので n のオーダーであり、
ステップ数:sは、 a^s = n より s = log(n) / log(a) なのでlog(n)のオーダー。
よって計算量はＯ(n*log(n))と見積もれる。
ただし、ギャップが１になった時点でソートがほぼ終わっていること。※１
それを満たさない特殊初期条件が存在しない事を証明できれば、
「コムソートの計算量はn*log(n)のオーダーです。」
と胸を張って言えるだろう(^-^;)
これはスタンダードなソートアルゴリズムと同等であり
処理の単純さにより「速い」ことになるが、
どのような初期条件でも一定して
これだけかかる事には留意する必要がある。
※１ 亀がm歩かかった場合、追加でＯ(n*m)かかる。
[ 付表 ]