shell sort

ところでどなたか、シェルソートがO(?)なのかご存じの方はいらっしゃらないでしょうか。O(n(log n)²)という人もいるし、O(n^1.25)という人もいるし....

http://blog.livedoor.jp/dankogai/archives/50962504.html

シェルソートは、挿入ソートを行う間隔の取り方で計算量が変わり、最悪計算量が O(n²) や O(n(log n)²) となる間隔の取り方が知られているようです。O(n^1.25) は良くわかりません。計算量が O(n log n) となるような間隔のとり方が存在するかどうかはまだ解かれていないようです。