挿入ソートの改良版です。最初から隣り合う要素同士を比較するのではなく、ある一定の「間隔（gap）」を空けた要素同士でグループを作り、それぞれのグループ内で挿入ソートを行います。間隔を徐々に狭めていき（最終的に gap=1）、最後に通常の挿入ソートを行って仕上げます。
計算量: 平均して O(N^1.25) ～ O(N^1.5) 程度（間隔の決め方に依存）
特徴: 挿入ソートの弱点である「小さい値が右端にあると移動に時間がかかる」問題を、遠くへジャンプさせることで解消しています。
シェルソート (Shell Sort)
JavaScript
共有コメント 共有されるコメント欄です。