この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "挿入ソート"
挿入ソートクラスソート
データ構造配列
最悪計算時間 O ( n 2 ) {\displaystyle O(n^{2})}
最良計算時間 O ( n ) {\displaystyle O(n)}
平均計算時間 O ( n 2 ) {\displaystyle O(n^{2})}
最悪空間計算量 O ( n ) {\displaystyle O(n)} total, O ( 1 ) {\displaystyle O(1)} auxiliary
挿入ソート（そうにゅうソート、英: insertion sort）あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。
時間計算量は平均・最悪ケースでともに Ο(n2) であり、クイックソートやマージソートなどと比べれば遅い。しかし、
アルゴリズムが単純で実装が容易
小さな配列に対しては高速
安定
in-placeアルゴリズム
オンラインアルゴリズム
などの特徴から利用されることがある。
挿入ソートを高速化したソート法として、シェルソートが知られている。 まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。 整列された部分（確定とは限らない）をアンダーライン、挿入する部分を太字で表す。84376521（初期データ） バブルソートと比較すると、「交換回数」は等しくなる。しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。 なお交換回数に関しても、前記実装例のように一連の交換の途中の特定処理を省略することができるので交換一回が高速になる。また、特にデータが連結リストで格納されている場合には、バブルソートと比較して大幅な高速化が図れる。これは配列における「挿入」が一連の交換（の途中の特定処理を省略した処理）によって実現されるのに対し、連結リストでは文字通りの「挿入」が可能であるので、交換回数が大幅に減少するからである。 挿入ソートの改良で、挿入するデータの前ではソートが済んでいるという性質を利用して、挿入する箇所を二分探索するというものである。データの量が少ないときにはあまり効果がないが、多いときには比較回数が少なくなる。探索アルゴリズムによっては不安定なソートになるが、工夫により安定させることが可能である。
アルゴリズム
動作例
48376521（1回目のループ終了時）
34876521（2回目のループ終了時）
34786521（3回目のループ終了時）
34678521（4回目のループ終了時）
34567821（5回目のループ終了時）
23456781（6回目のループ終了時）
12345678（7回目のループ終了時。ソート完了）
実装
C言語void insertion_sort(int data[], size_t n) { for (size_t i = 1; i < n; i++) { if (data[i - 1] > data[i]) { size_t j = i; int tmp = data[i]; do { data[j] = data[j - 1]; j--; } while (j > 0 && data[j - 1] > tmp); data[j] = tmp; } }}
Scheme(define (insertion-sort ls) (define (insert x ls) (let loop ((ls ls) (acc '())) (if (null? ls) (append acc (cons x ls)) (let ((y (car ls))) (if (< x y) (append (reverse acc) (cons x ls)) (loop (cdr ls) (cons y acc))))))) (let loop ((ls ls) (acc '())) (if (null? ls) acc (let ((x (car ls))) (loop (cdr ls) (insert x acc))))))
計算時間
二分挿入ソート
表
話
編
歴
ソート
理論
計算複雑性理論
ランダウの記号
全順序
リスト
安定性
ソーティングネットワーク
比較ソート
整数ソート（英語版）
交換ソート
バブルソート
シェーカーソート
奇偶転置ソート
コムソート
ノームソート
クイックソート
選択ソート
選択ソート
ヒープソート
スムースソート
デカルト木ソート
トーナメントソート
挿入ソート
挿入ソート
シェルソート
ツリーソート
図書館ソート
ペイシェンスソート
マージソート
マージソート
多層マージソート
ストランドソート
非比較ソート
基数ソート
バケットソート
計数ソート
プロキシマップソート
鳩の巣ソート
バーストソート
ビーズソート
並行ソート
バイトニックソート
バッチャー奇偶マージソート
シェアソート
混成ソート
ティムソート
イントロソート
Jソート
アンシャッフルソート（英語版）
その他
トポロジカルソート
パンケーキソート
スパゲティソート
非効率的/
ユーモラスソート
ボゴソート
ストゥージソート
スリープソート
エラーソート
カテゴリ
