挿入ソートは、未整列の要素を 1 つ取り出し、すでに整列済みの部分の適切な位置に挿入することを繰り返すソートアルゴリズムです。トランプを手札に並べていく動作に似ています。
| 観点 | 挿入ソート |
|---|---|
| 計算量（平均・最悪） | |
| 計算量（ほぼ整列済み） | |
| 長所 | 小規模・整列済みに強い |
| 短所 | 乱雑な大量データは遅い |
「3, 5 | 1」のように整列済み部分があれば、次の 1 を前へずらして「1, 3, 5」と挿入します。すでにほぼ並んでいるデータでは と高速なので、実用ライブラリでも小さな部分配列のソートに使われます。
たとえば「3, 5」まで整列済みのところへ 1 が来たら、3 と 5 を 1 つずつ後ろへずらして先頭に 1 を差し込み、「1, 3, 5」にします。すでにほぼ並んでいれば、ずらす回数が少なくて済みます。
試験では 「整列済み部分に挿入する」手順と、ほぼ整列済みデータに強い点が問われます。
