挿入ソート — Project Hematite

トランプ手札をソートする場面を想像しよう。テーブルから 1 枚ずつカードを拾い、次に小さいカードの後ろに収まるまで手の中で左にスライドする。それが挿入ソートだ：シンプルで、ほぼソート済みの入力に対して $O(n)$ であり、Timsort のような実用的なハイブリッドソートが小さいサブ配列に使うほど高速だ。

アルゴリズム

挿入ソートはソート済み前半部分 arr[0..i] を維持する。各ステップで位置 i の要素（key と呼ぶ）を取り、ソート済み前半部分のより大きい要素を 1 ステップ右にシフトし、key を空いた場所に入れる。

fn insertionSort(arr: []i64) void {
    var i: usize = 1;
    while (i < arr.len) : (i += 1) {
        const key = arr[i];
        var j = i;
        // key より大きい要素を 1 位置右にシフトする。
        while (j > 0 and arr[j - 1] > key) : (j -= 1) {
            arr[j] = arr[j - 1];
        }
        arr[j] = key;
    }
}

内側の while ループは key 以下の要素を見つけた時点か、配列の先頭に達した時点で終了する。arr[j] = key で key を正しい位置に配置する。

ループ不変条件による正しさの証明

不変条件：反復 $i$ の開始時に、arr[0..i] はソートされている。

反復 1 の前（ $i = 1$ ）：arr[0..1] は要素 1 つ — 自明にソートされている。
維持：内側のループは arr[0..i] 内の key より大きい要素をすべて 1 ステップ右にシフトして正しい挿入位置 $j$ を見つける。arr[j] = key の後、前半部分 arr[0..i+1] はソートされており、 $i+1$ に対して不変条件が再確立される。
終了： $i$ は各反復で増加し arr.len に達する。その時点で不変条件は arr[0..arr.len] — 配列全体 — がソートされていると述べる。

安定性

挿入ソートは安定だ：内側のループは key より厳密に大きい要素のみをシフトする。key と等しい要素はシフトを止め、key はその直後に挿入されるため、元の相対順序が保たれる。

計算量

最悪ケース：逆ソートされた入力

配列が逆順にソートされている場合、すべての新しい要素が位置 0 まで移動する必要がある。反復 $i$ は $i$ 回のシフトを行う：

1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2} = \Theta(n^2).

最良ケース：ソート済み入力

配列がすでにソートされている場合、すべての key は即座に arr[j - 1] <= key を満たす — 内側のループは 0 回反復する。総仕事量： $n - 1$ 回の比較、 $O(n)$ 。

一般ケース：転倒数

転倒（inversion）とは $i < j$ かつ arr[i] > arr[j] を満たすインデックスのペア $(i, j)$ だ。内側のループの各シフトはちょうど 1 つの転倒を解消する。よって挿入ソートは入力の転倒数とちょうど同じ回数のシフトを行う。

ソート済み入力：転倒 0 → $O(n)$ シフト。
ほぼソート済み（要素あたり最大 $k$ 転倒）： $O(kn)$ シフト。
逆ソート： $\binom{n}{2}$ 転倒 → $\Theta(n^2)$ シフト。

この転倒ベースの見方が、入力がほぼソートされている場合に挿入ソートが最適な選択である理由を説明する。

ケース	比較回数	シフト回数
最良（ソート済み）	$O(n)$	$0$
最悪（逆ソート）	$\Theta(n^2)$	$\Theta(n^2)$
平均	$\Theta(n^2)$	$\Theta(n^2)$

空間計算量は $O(1)$ ：配列に加えて key と j だけが必要だ。

挿入ソートが実用的な理由

$O(n^2)$ の最悪ケースにもかかわらず、挿入ソートは小さい配列ではマージソートとクイックソートを上回る。以下の特徴がある：

再帰オーバーヘッドなし — 外側のループを超えたコールスタックフレームがない。
補助メモリなし — マージソートは $O(n)$ の余分な空間が必要だ。
優秀なキャッシュ挙動 — 内側のループは連続したメモリアドレスを読み書きする。

多くの言語（Go、Java、Python の Timsort）の標準ライブラリソートは、サブ配列が概ね 10〜32 要素を下回ると $O(n \log n)$ アルゴリズムから挿入ソートに切り替える。

まとめ

挿入ソートは右シフトによって各新しい要素を正しい位置に挿入することでソート済み前半部分を維持する。
安定だ：等しい要素は並び替えられない。
最良ケース時間は $O(n)$ （ソート済み入力）、最悪ケースは $\Theta(n^2)$ （逆ソート）。
シフト回数は入力の転倒数に等しく、要素あたり最大 $k$ 転倒のデータに対して $O(kn)$ になる。
空間は $O(1)$ 、再帰はない。
Timsort のような実用的なハイブリッドソートの小配列サブルーチンとして使われる。