シェルソート（改良挿入ソート、）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。ドナルド・シェル（Donald L. Shell）が、1959年に、シェルソートの最初のバージョンを公開した 。シェルソートの実行時間は、比較時に選ぶ間隔によって大きく異なる。多くの実用的な方法が提案されているが、正確な時間計算量を求める方法は、未解決問題である。基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という特長があるものの、「隣り合った要素同士しか交換しない」ため、あまり整列されていないデータに対しては低速であった。そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソートしておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適用したのがシェルソートである。初期データ: 間隔4でみる。色の同じところは、同じグループのデータ列である。同じグループ内で挿入ソートし、間隔を2にする。同じグループ内で挿入ソートし、間隔を1にする。間隔1ということは、全体が同じ1つのグループということである。これを挿入ソートする。データの個数を formula_5 とすると、計算時間は以下のようになる。※ 間隔 formula_1 として、 formula_7 という formula_8 を満たす整数列を大きい方から採用すると、平均計算時間 formula_9 になる。

出典:wikipedia