Aizu Online Judge の Shell Sort の問題 をやってて、なんか分かった気がしないなぁと思ってました。
Aizu Online Judgeの一部の問題は、本だと解説されてたりします。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者:渡部 有隆
- 発売日: 2015/01/30
- メディア: Kindle版
計算量もどうしたらいいんだろと調べたところ、単純ではないようです。
まずは雰囲気だけでもサクッと...と思ってJavaScriptで挿入ソートとシェルソートを並べてみました。うむ、確かにシェルソートの方が速くソートできてる。
See the Pen Insertion Sort & Shell Sort by bati11 (@bati11) on CodePen.