挿入ソートの計算量は？最悪・平均・最良時も！（O(n²)・安定ソート・内部ソート・小さなデータセットなど）

プログラミングを学ぶうえで必ず触れることになるのが挿入ソートです。

挿入ソートは、トランプを手に取って並べ替えるような直感的なアルゴリズムで、シンプルな実装と安定ソートという特性から、今でも重要なアルゴリズムのひとつです。

本記事では、挿入ソートの計算量について最悪ケース・平均ケース・最良ケース別に詳しく解説し、O(n²)となる理由・安定ソートとしての特性・内部ソートとしての利点・小さなデータセットへの適性まで丁寧に説明していきます。

基礎的なアルゴリズム学習から実務での使い分けまで、ぜひ参考にしてください。

挿入ソートの計算量はO(n²)（最悪・平均）（結論）

それではまず、挿入ソートの計算量とその理由について解説していきます。

挿入ソートの時間計算量は、最悪ケースと平均ケースでO(n²)、最良ケースでO(n)です。

挿入ソートの動作は、未ソート部分の先頭要素を取り出し、ソート済み部分の正しい位置に挿入するという操作を繰り返します。

最悪ケースは、入力が逆順に並んでいる場合です。

各ステップで、挿入対象の要素をソート済み部分の先頭まで比較・移動する必要があり、操作数は1+2+3+…+(n-1) = n(n-1)/2となります。

これはO(n²)です。

平均ケースも同様にO(n²)です。

ランダムな配列では、各要素を挿入する際に平均してソート済み部分の半分を移動する必要があるため、合計はn(n-1)/4となりやはりO(n²)です。

ケース別計算量のまとめ

ケース	入力の状態	時間計算量
最良	すでにソート済み	O(n)
平均	ランダム	O(n²)
最悪	逆順にソート済み	O(n²)

空間計算量はO(1)です。

挿入ソートは追加の配列を必要とせず、元の配列の中だけで要素を移動するため、補助空間は定数量で済みます。

O(n²)の直感的な説明

O(n²)が直感的にイメージしにくい場合は、「n人のプレイヤーが全員1回ずつ対戦する総当たり戦」と考えると理解しやすいでしょう。

n人の総当たりは n(n-1)/2 試合 ≒ n²/2 となり、これがO(n²)の計算量に対応します。

挿入ソートも最悪ケースでは、後から来た要素がそれまでの全要素と比較・移動するため、同じような構造になります。

挿入ソートの安定ソートとしての特性

挿入ソートは安定ソートです。

等しい値を持つ要素を挿入する際、すでにソート済みの部分で同じ値の要素より後ろに挿入されます。

つまり、元の順序が保持されるため、安定性が自然に実現されています。

挿入ソートのアルゴリズムと実装

続いては、挿入ソートの具体的なアルゴリズムと実装方法を確認していきます。

アルゴリズムの詳細な手順

挿入ソートのアルゴリズムは以下の手順で進みます。

この操作はトランプの手札を整理するときのイメージと同じです。

左の手札が常にソート済みの状態を保ちながら、右から1枚ずつ正しい位置に差し込んでいきます。

Pythonでの実装

このコードはシンプルで理解しやすく、コード量も少ないです。

実装の単純さは挿入ソートの大きな利点の一つと言えるでしょう。

比較回数と移動回数の分析

挿入ソートの操作は「比較」と「移動（シフト）」の2種類に分けられます。

比較回数は最悪O(n²)・最良O(n)ですが、移動回数も同様に最悪O(n²)・最良O(0)です。

最良ケースでは比較はn-1回行われますが、移動は一切発生しないという特徴があります。

これがO(n)の最良ケース計算量を実現する理由です。

内部ソートとしての利点と適用場面

続いては、挿入ソートが内部ソートとして持つ利点と、実際に適用すべき場面について確認していきます。

内部ソートとは何か

内部ソート（in-place sort）とは、ソートに必要な追加メモリがO(1)（定数量）であるソートアルゴリズムのことです。

挿入ソートは補助配列を使わず、元の配列内で要素を移動するだけでソートが完了するため、典型的な内部ソートです。

メモリが制限された環境（組み込みシステムやマイコンなど）では、空間計算量O(1)の内部ソートが非常に重要です。

挿入ソートはO(1)の空間計算量と安定性を両立できる数少ないアルゴリズムです。

小さなデータセットへの適性

挿入ソートはO(n²)の時間計算量を持ちますが、小さなデータセット（一般的にはn≦20程度）では驚くほど高速に動作します。

その理由として、まずオーバーヘッドが非常に小さいことが挙げられます。

再帰呼び出しのコストがなく、単純なループとシフト操作のみで動作します。

次に、キャッシュフレンドリーであることです。

隣接メモリへのアクセスが中心なのでCPUキャッシュを有効に使えます。

また、実装が単純で分岐予測も立てやすいです。

データ規模	推奨アルゴリズム	理由
n < 20（小）	挿入ソート	オーバーヘッドが最小
20 ≦ n < 1000（中）	クイックソート or Timsort	実測で高速
n ≧ 1000（大）	マージソート or Timsort	O(n log n)の保証が重要

ハイブリッドアルゴリズムへの組み込み

挿入ソートの「小さいデータに強い」特性は、高度なソートアルゴリズムに取り込まれています。

Timsortは、配列をチャンクに分割し、小さいチャンクに挿入ソートを適用してからマージするハイブリッドアルゴリズムです。

introsortは、基本的にクイックソートで処理し、再帰が深くなりすぎたらヒープソートに切り替え、小さいデータには挿入ソートを使うアルゴリズムです。

挿入ソートは「補助的な高速化ツール」として現代の実用的なソートに組み込まれています。

挿入ソートの改良版と他のO(n²)ソートとの比較

続いては、挿入ソートの改良版と他のO(n²)ソートアルゴリズムとの比較について確認していきます。

シェルソート（Shell Sort）

シェルソートは挿入ソートを改良したアルゴリズムです。

挿入ソートの弱点である「要素が大きく離れた位置に移動するのに多くのステップが必要」という問題を、最初に大きなギャップで比較・交換することで解決します。

ギャップを段階的に小さくしながら最終的にギャップ1（通常の挿入ソート）で仕上げます。

シェルソートの計算量はギャップシーケンスに依存しますが、最良の場合O(n log² n)程度まで改善できます。

バブルソートとの比較

バブルソートも最悪・平均O(n²)のアルゴリズムですが、挿入ソートとは動作が異なります。

バブルソートは隣接要素を比較・交換することで大きな要素を末尾に「浮かび上がらせる」動作を繰り返します。

一般に、挿入ソートはバブルソートより高速です。

その理由は、挿入ソートは早期終了（ソート済みなら比較を止める）がしやすいのに対し、バブルソートは最良ケースでも最適化なしにO(n²)になりやすいからです。

選択ソートとの比較

選択ソートは未ソート部分から最小値を選んで先頭に移動する操作を繰り返すアルゴリズムです。

最悪・平均・最良のすべてでO(n²)の比較が必要で、最良ケースでもO(n)にはなりません。

また選択ソートは不安定ソートであるため、安定性が必要な場面では使いにくいです。

アルゴリズム	最良	平均	最悪	安定性	空間
挿入ソート	O(n)	O(n²)	O(n²)	安定	O(1)
バブルソート	O(n)	O(n²)	O(n²)	安定	O(1)
選択ソート	O(n²)	O(n²)	O(n²)	不安定	O(1)

O(n²)のソートの中では、挿入ソートが最も優れた最良ケース（O(n)）を持ち、安定性も備えているため、総合的に最もバランスが良いと言えるでしょう。

まとめ

挿入ソートの時間計算量は最悪・平均でO(n²)、最良ケースではO(n)です。

空間計算量はO(1)であり、追加のメモリをほとんど必要としない内部ソートです。

安定ソートとしての特性を持ち、等しい値の要素の順序を保持します。

大規模なデータには不向きですが、小さいデータセット（n≦20程度）やほぼソート済みのデータに対しては非常に効率的で、実測でも高速です。

TimsortやIntrosortといった現代の高性能ソートアルゴリズムにも部品として組み込まれており、実用的な価値は今でも高いです。

シンプルな実装と安定性・低空間計算量という特性を正しく理解し、適切な場面で活用してみてください。