挿入ソート入門：仕組み・計算量・実装例と実用的な最適化ポイント

挿入ソートとは

挿入ソート（Insertion Sort）は、簡潔で理解しやすい比較ソートの一種です。配列の先頭から順に要素を「既に整列済みの部分列」に挿入していく方式を取り、手でトランプを並べ替える動作に似ています。実装が容易で、小さい配列やほぼ整列済みのデータに対しては非常に高速に動作します。

アルゴリズムの基本原理

挿入ソートは次のような手順で動作します。

• 配列の先頭要素を整列済みの部分列（長さ1）とみなす。
• 未処理の次の要素を取り出し、整列済み部分列の適切な位置へ挿入する（要素を右へシフトして空きを作る）。
• これを配列末尾まで繰り返す。

具体例：配列 [5, 2, 4, 6, 1, 3] の場合、2 を 5 の前に挿入 → [2,5,4,6,1,3]、次に 4 を [2,5] に挿入 → [2,4,5,6,1,3] … と進みます。

典型的な実装（擬似コード）

for i = 1 to n-1:
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]   # 右へシフト
        j = j - 1
    A[j+1] = key      # key を挿入

計算量と性質

• 時間計算量（比較・シフトの観点）
  • 最良ケース：O(n) — 配列が既に整列済みであれば各要素は1回の比較で済む。
  • 平均ケース：O(n^2)
  • 最悪ケース：O(n^2) — 例えば逆順に並んでいる場合、各挿入で多くのシフトが必要。
• 空間計算量：O(1)（インプレース、追加の配列をほとんど使わない）
• 安定性：安定（等しいキーの要素は元の順序を保つ）— 比較条件を ">" のみで行い等しい場合に移動させない実装に限る。
• 適応性（Adaptive）：入力が既に部分的に整列している場合に高速（挿入に必要な移動回数が入力の逆順ペア数に依存）。
• オンライン性：オンラインに処理可能（順に要素を受け取りながらソートを進められる）。

挿入ソートと逆順ペア（inversions）の関係

入力配列に含まれる逆順ペア（i < j で A[i] > A[j] となるペア）の数を k とすると、挿入ソートの実行時間は Θ(n + k) と表現できます。逆順ペアが少ない（ほぼ整列済み）場合、k が小さくなり高速に動作することがわかります。一方、逆順ペアが最大（逆順ソート）であれば k = Θ(n^2) となります。

比較回数と移動回数の違い（バイナリ挿入ソートの考察）

挿入ソートは通常、挿入位置を決めるために線形探索を行うため比較回数も O(n^2) です。バイナリ検索で挿入位置を見つける変種（バイナリ挿入ソート）を使えば比較回数は O(n log n) に減りますが、配列内の要素の移動（シフト）は依然としてO(n^2)で、総合的な時間は依然としてΘ(n^2)です。つまり、比較回数の最適化はできてもデータ移動がボトルネックとなる場合は全体のオーダーは改善されません。

改良点と派生アルゴリズム

• センチネル（番兵）を先頭に置く：境界チェック（j >= 0）を減らして若干高速化。
• バイナリ挿入ソート：挿入位置の探索に二分探索を用いる（比較回数削減）。
• シェルソート：ギャップで分割した部分列に対して挿入ソートを適用することで、平均実行時間を大幅に改善することができる。
• ハイブリッド手法：クイックソートやマージソートのような分割統治系アルゴリズムの小さいサブ配列を処理する際に挿入ソートを使う（実用的な閾値で性能向上）。例：Timsort や Introsort の小配列処理。

実用上の使いどころ

• データ量が非常に小さい場合（n が数十程度以下）：オーバーヘッドが少ないため、実際には高速。
• ほぼ整列済みのデータ：逆順ペアが少なく、ほぼ線形時間で処理可能。
• 安定性・インプレース性が必要な場面：メモリ制約が厳しい場合に有利。
• オンライン処理：ストリーム状にデータが入ってくる場面で逐次挿入していく用途。

他のアルゴリズムとの比較（概観）

• Selection Sort：選択ソートは比較回数がΘ(n^2)で移動回数が少ない（スワップ回数が少ない）。挿入ソートはほぼ整列時に有利。
• Bubble Sort：バブルソートもΘ(n^2)だが、挿入ソートの方が実用面で優れることが多い。
• Merge/Quick/Heap：これらは平均・最良で O(n log n) を実現する。大規模データやランダムデータにはこれらが適切。だが小配列やほぼ整列済みでは挿入ソートの方が速いことが多い。

実装のポイントと注意点

• 安定性を保つため、等しい要素は移動させない実装（while の条件を A[j] > key のままにする）にする。
• 配列のシフト操作はコストが高いため、要素のコピー回数を減らす工夫（キーを一時保存してシフト）を行う。
• 大きなデータ型を頻繁にコピーする場合は、参照やポインタを扱う実装を検討するとよい。

サンプル実装（JavaScript）

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    // A[j] > key の条件で等しい要素は動かさない → 安定性を維持
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

視覚的理解のコツ

挿入ソートを理解するには、配列の左半分を「整列済み」と意識して手でカードを並べるイメージが有効です。各ステップで一つのカード（要素）を取り出し、左の正しい位置へ挿していく。視覚化ツールで要素の比較とシフトを観察すると、どのように逆順ペアが解消されていくかが分かりやすくなります。

まとめ

挿入ソートはアルゴリズム教育で最初に学ぶソートの一つで、シンプルさと実用性を併せ持ちます。理論的には O(n^2) のアルゴリズムですが、小規模データやほぼ整列済みのデータ、オンライン処理、あるいはハイブリッドソートの一部としては非常に有効です。バイナリ探索やセンチネル、シェルソートなどの改良や派生を通して実用性を高める余地も多くあります。

参考文献

• Insertion sort — Wikipedia
• Insertion Sort — CP-Algorithms
• MIT OCW: Insertion Sort and Runtimes
• Timsort — Wikipedia (ハイブリッド手法での挿入ソートの利用例)
• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms（CLRS） — Sorting の章