シェルソート
アルゴリズムの基本は挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速であった。 シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿入ソートの長所を活かしたものである。 アルゴリズムの概略は次のとおりである。
適当な間隔 h {\displaystyle h} を決める(hの決め方については後述)
間隔 h {\displaystyle h} をあけて取り出したデータ列に挿入ソートを適用する
間隔 h {\displaystyle h} を狭めて、2.を適用する操作を繰り返す
h = 1 {\displaystyle h=1} になったら、最後に挿入ソートを適用して終了