Hello Algoで学ぶ挿入ソート（insertion sort）完全ガイド：アルゴリズムの流れ・実装コード・計算量・実用優位性を徹底解説

挿入ソート（insertion sort）は、トランプの手札を小さい順に整理するのとそっくりな、最も直感的に理解できるソートアルゴリズムです。本記事では『Hello Algo』日本語版リポジトリの insertion_sort.md と各言語の実装コードを題材に、「未ソート区間から要素を1つ取り出し、整列済み区間の正しい位置に挿入する」という仕組みを、図解・逐行解説・計算量の導出まで丁寧に紐解きます。さらに「なぜ $O(n^2)$ なのに挿入ソートは実務で重用されるのか」「バブルソートや選択ソートと何が違うのか」という実用視点の疑問にも答え、読了後には挿入ソートを使いどころ込みで理解できるようになります。

挿入ソートの基本概念：手札を整える操作を配列で再現する

挿入ソートは単純なソートアルゴリズムであり、その動作原理は手作業でトランプの山札を整える過程と非常によく似ています。

具体的には、未ソート区間から基準要素（base）を1つ選び、その要素を左側の整列済み区間の要素と1つずつ比較し、正しい位置に挿入します。

上の図は、配列に1要素を挿入する操作の流れを示しています。基準要素を base とすると、次が必要な3ステップです。

1. base を一時的に退避する（Temporarily store base）。
2. 目標インデックスから base があった位置までのすべての要素を、1つずつ右へ移動する（Move elements one position back）。
3. 空いた目標インデックスに base を代入する（Assign the element to the target index）。

この「退避 → 右シフト → 代入」という単一挿入操作を配列の先頭から末尾まで繰り返すのが挿入ソート全体の戦略です。なお、要素を代入で移動する点は後述するように挿入ソートの性能上の大きな強みになります。

アルゴリズムの流れ：整列済み区間を1要素ずつ伸ばしていく

挿入ソート全体の流れを以下の図に示します。灰色の部分が「整列済み（ソート済み）区間」で、1ラウンドごとに右へ1つずつ拡大していきます。

手順を番号で整理すると次のとおりです。

1. 初期状態では、配列の1番目の要素はすでに整列済みとみなします。
2. 配列の2番目の要素を base として選び、正しい位置に挿入すると、配列の先頭2要素が整列済みになります。
3. 3番目の要素を base として選び、正しい位置に挿入すると、配列の先頭3要素が整列済みになります。
4. このように繰り返し、最後のラウンドで最後の要素を base として選んで正しい位置に挿入すると、すべての要素が整列済みになります。

つまり外側ループの各ラウンド $i$ が始まる時点では、区間 $[0, i-1]$ が整列済みであり、$i$ を0から $n-1$ まで進めるたびに「整列済み区間の右端が1つ伸びる」というループ不変式が成り立ちます。これを不変式として意識しておくと、後述のコードが「なぜ常に正しく整列するのか」を直感的に把握できます。

リポジトリの実装コードを逐行解説する

日本語版リポジトリにはこのアルゴリズムが Python実装 をはじめ、C / C++ / C# / Dart / Go / Java / JavaScript / Kotlin / Python / Ruby / Rust / Swift / TypeScript / Zig の全言語で同一ロジックで用意されています。ここでは日本語版 Pythonコード を例に、各処理が上述の流れとどう対応するかを見ていきます。

def insertion_sort(nums: list[int]):
    """挿入ソート"""
    # 外側ループ：整列済み区間は [0, i-1]
    for i in range(1, len(nums)):
        base = nums[i]
        j = i - 1
        # 内側ループ: base をソート済み区間 [0, i-1] の正しい位置に挿入する
        while j >= 0 and nums[j] > base:
            nums[j + 1] = nums[j]  # nums[j] を 1 つ右へ移動する
            j -= 1
        nums[j + 1] = base  # base を正しい位置に配置する

ポイントを変数単位で解説します。

• 外側ループ（for i in range(1, len(nums))）：i は「これから挿入する要素の位置」を表します。i=1（2番目の要素）から開始し、先頭要素だけは初期状態で整列済みとみなすためです。ラウンドごとに整列済み区間が [0, 0] → [0, 1] → … → [0, n-1] と伸びていきます。
• base = nums[i]：未ソート区間の先頭要素を取り出し、退避します。これが図中の「一時退避」に相当します。後の右シフトで nums[i] の値が上書きされても大丈夫なようにしています。
• j = i - 1：内側ループの探索を整列済み区間の右端（i の直前）から始めます。
• 内側ループ（while j >= 0 and nums[j] > base）：整列済み区間を右から左へ走査しながら、base より大きい要素を見つけるたびに nums[j + 1] = nums[j] で1つ右へ移動します。j >= 0 の条件により、配列の先頭（左端）を越えてアクセスしないことを保証します。
• nums[j + 1] = base：base 以下の要素に到達（または先頭まで到達）した時点の1つ右の位置が base の正しい挿入先です。ここへ退避していた base を代入します。

比較演算子が >（より大きい）であることに注目してください。等しい要素に対しては右シフトが発生しないため、base は必ず「等しい値の右側」に挿入されます。これが挿入ソートの安定性（後述）を支える実装上の要点です。

参考までに、同じロジックを静的な型を持つ Java実装 で書くと次のようになります。コメントも日本語版で整備されています。

/* 挿入ソート */
static void insertionSort(int[] nums) {
    // 外側ループ：整列済み区間は [0, i-1]
    for (int i = 1; i < nums.length; i++) {
        int base = nums[i], j = i - 1;
        // 内側ループ: base をソート済み区間 [0, i-1] の正しい位置に挿入する
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // nums[j] を 1 つ右へ移動する
            j--;
        }
        nums[j + 1] = base;        // base を正しい位置に配置する
    }
}

実行例でラウンドごとの変化を追う

日本語版の各実装にはドライバコードが付属しており、Python版 では入力配列 nums = [4, 1, 3, 1, 5, 2] を用います。上の全体フロー図と同じ入力であり、各ラウンドの整列済み区間は次のように推移します（| の左が整列済み区間）。

ラウンド	base	処理後の配列	整列済み区間
初期状態	—	`[4	1, 3, 1, 5, 2]`
第1ラウンド（i=1）	1	`[1, 4	3, 1, 5, 2]`
第2ラウンド（i=2）	3	`[1, 3, 4	1, 5, 2]`
第3ラウンド（i=3）	1	`[1, 1, 3, 4	5, 2]`
第4ラウンド（i=4）	5	`[1, 1, 3, 4, 5	2]`
第5ラウンド（i=5）	2	[1, 1, 2, 3, 4, 5]	[0, 5]

同じ値の 1 が2つあっても、後から挿入された 1 は常に既存の 1 の右側に置かれる点に注目してください（第3ラウンド）。等値要素の相対順序が保たれるため、挿入ソートは安定ソートとして振る舞います。

実際に手元で動作を確認したい場合は、以下のコマンドで実行できます（リポジトリルートから実行した場合の出力例付き）。

python3 ja/codes/python/chapter_sorting/insertion_sort.py

挿入ソート完了後 nums = [1, 1, 2, 3, 4, 5]

また、ステップごとの変数変化をブラウザ上で可視化しながら追いたい場合は、日本語版の PythonTutor用ファイル を参照してください。

挿入ソートのアルゴリズム特性：計算量・空間・安定性

挿入ソートの特性を整理すると以下のとおりです。

• 時間計算量は $O(n^2)$・適応的ソート：最悪の場合（入力が降順など、毎回 base が整列済み区間の全要素と比較される場合）、各挿入操作ではそれぞれ $n - 1$、$n - 2$、$\dots$、$2$、$1$ 回のループが必要であり、合計は $\frac{(n-1)n}{2}$ となります。したがって時間計算量は $O(n^2)$ です。一方、データがすでに整列済みであれば挿入操作は早期に終了します。入力配列が完全に整列済みである場合、内側ループは各ラウンドで一度も回らず、挿入ソートは最良の時間計算量 $O(n)$ に到達します。この「入力の整列度合いに応じて計算時間が変わる」性質を**適応的（adaptive）**と呼びます。
• 空間計算量は $O(1)$・インプレースソート：追加で確保するのはポインタ（インデックス）$i$ と $j$、そして退避用の base という定数サイズの追加領域のみです。元の配列を破壊的に並べ替えるため、配列のサイズに依存する追加メモリは一切必要ありません。
• 安定ソート：挿入操作の過程では、要素を等しい要素の右側に挿入するため、等値要素どうしの相対的な順序は変化しません。安定性は後述する「多段ソート」への応用で重要になります。

特性を一覧表にまとめると次のようになります。

指標	挿入ソートの値
平均・最悪の時間計算量	$O(n^2)$
最良の時間計算量	$O(n)$（入力が完全に整列済みのとき）
空間計算量	$O(1)$
ソート方式	インプレースソート（追加配列不要）
適応性	適応的（整列度に応じて高速化）
安定性	安定

なぜ挿入ソートが実務で重用されるのか：3つの優位性

挿入ソートの時間計算量は $O(n^2)$ であり、後に学習する クイックソート の時間計算量は $O(n \log n)$ です。挿入ソートの時間計算量のほうが大きいにもかかわらず、データ量が小さい場合には挿入ソートのほうが通常は高速です。この逆説を理解することが、本節の主眼です。

優位性1：小規模データでは $O(n \log n)$ アルゴリズムより速い

この結論は、線形探索と二分探索の適用条件に関する結論と似ています。クイックソートのような $O(n \log n)$ のアルゴリズムは**分割統治法（分而治之）に基づくソートアルゴリズムであり、再帰やピボット分割といったより多くの基本演算（単位操作）**を含みます。一方、データ量 $n$ が小さい場合は、$n^2$ と $n \log n$ の値は比較的近く、計算量の漸近的な差が支配的ではなくなります。その代わり、各ラウンドで実行される基本演算（比較・代入）の回数が実行時間を決定的に左右するようになるのです。その結果、オーバーヘッドの小さい挿入ソートが小規模入力で逆転勝利します。

実際、多くのプログラミング言語（たとえば Java）の組み込みソート関数では挿入ソートが採用されており、その大まかな考え方は次のとおりです。長い配列にはクイックソートなどの分割統治ベースのソートアルゴリズムを使い、短い配列には直接挿入ソートを使うというハイブリッド戦略です。再帰の末端で細切れになった部分配列を、毎回オーバーヘッドの大きい高速ソートで処理するのは非効率なので、閾値以下の区間を挿入ソートで締めくくるのが定石となっています。

優位性2：バブルソートより計算コストが低い

バブルソート・選択ソート・挿入ソートはいずれも時間計算量が $O(n^2)$ ですが、実際には挿入ソートはバブルソートや選択ソートよりもはるかに高い頻度で使われます。その第一の理由は「単位操作の数」です。

• バブルソートは要素の交換によって実装され、交換のたびに1つの一時変数が必要になるため、合計で3回の基本演算（退避・代入・書き戻し）が関わります。
• これに対して挿入ソートは要素の代入に基づいており、右シフトに必要な基本演算は1回だけです。

したがって、バブルソートの計算コストは通常、挿入ソートより高くなります。同じ $O(n^2)$ でも「3回の操作を伴う交換」を繰り返すバブルソートと、「1回の代入」で済む挿入ソートでは、定数係数に明確な差が生じます。

優位性3：選択ソートより部分整列データに強い／安定性がある

• 選択ソートの時間計算量はどのような場合でも $O(n^2)$ です（「最小値を探し続ける」という構造上、入力の状態に依らず毎回全区間を走査します）。一方、挿入ソートは適応的であり、内側ループが base より大きい要素にだけ働きます。部分的に整列されたデータが与えられた場合、挿入ソートは通常、選択ソートより効率的です。極端な例として「すでにほぼ整列済みで、末尾に少数の乱れ要素だけがある」データでは、挿入ソートはほぼ $O(n)$ に近い速度を発揮します。
• 選択ソートは安定ではないため、多段ソートには適用できません。たとえば「まず部門でソートし、次に給与でソートする」といった複数キーによる多段ソートでは、安定ソートでなければ前段のソート結果が後段で壊れてしまいます。挿入ソートは安定なので、こうした用途にそのまま使えます。

まとめ：挿入ソートを選ぶべき状況

以上の議論を踏まえると、挿入ソートが真価を発揮するのは次のような状況です。

• データ量が小さい（数十要素程度）場合
• データが部分的に整列済みである場合（実質 $O(n)$ に近づく）
• 安定性が要求される、あるいは組み込みソートの内部補助（ハイブリッド戦略の末端処理）として

逆に、大規模・ランダムなデータに対しては $O(n\log n)$ のクイックソートやマージソートを選択するのが適切です。各ソートアルゴリズムの特性比較や使い分けの全体像は ソートアルゴリズム総論 に整理されています。

参考：この章の関連リソース

本記事の内容をさらに掘り下げるには、日本語版リポジトリ内の以下の資料が役立ちます。

• ソートアルゴリズム全体の比較：sorting_algorithm.md
• 同じ $O(n^2)$ 系で比較対象となる バブルソート と 選択ソート
• 小規模データでの対比相手である クイックソート
• 章末の練習問題：exercises.md、章サマリ
• 実装コード（日本語版）：Python / Java をはじめ、各言語版（C、C++、C#、Go、JavaScript、Rust、TypeScript ほか）

挿入ソートは「配列を左から順に整列済み区間へ差し込んでいく」という単純な戦略ながら、適応性・安定性・定数係数の小ささという実務で重要な性質を兼ね備えた稀有な $O(n^2)$ ソートです。この記事で、図による直観・コードによる実装・計算量による理論・そして「いつ使うべきか」という実用判断の4点が揃えば、挿入ソートはあなたの武器のひとつになるはずです。次はハイブリッドソートの観点から クイックソート を学び、$O(n \log n)$ の世界へ進むことをおすすめします。