挿入ソートを使用する

挿入ソート (insertion sort) は、先頭側の すでに整列済みの部分配列 を拡張しながら、未処理の要素を 先頭側の並びへの挿入位置 が見つかるまでひとつずつ先頭へ寄せていく比較ソートである。

  1. 整列済み領域: 最初は先頭要素だけを整列済みとみなす（長さ 1 の配列は自明に整列済み）。
  2. 対象: 続くインデックス i = 1, 2, … の要素を、この時点で整列済みの区間 [0, i-1] に取り込む。
  3. 挿入位置の探索: a[i] を キー と見て、キーより大きい隣接要素がある限り、その要素を先頭側へ繰り上げ（または隣接交換で等価な操作として）キーが収まる位置まで動かす。
  4. 終了: キーを空いた位置へ置いたら、[0, i] が整列済みとなる。すべての i について繰り返す。

実装によっては繰り上げを代入で書くほうが読みやすく、視覚化では 隣接スワップ で同じ並びになる例が多い。以下は隣接比較と交換で表現したアルゴリズムである。

procedure insertion_sort(A)
  n = length(A)
  for i from 1 to n - 1
    j = i
    while j > 0 and A[j - 1] > A[j] then
      swap(A[j - 1], A[j])
      j = j - 1

最悪・平均は比較回数ともに O(n²)。すでに昇順に近い入力では内部のループが早く終わり 最良は約 O(n)。追加配列なしなら O(1) の補助空間。安定ソート（等しい値の順序が保てる）。

小さな長さにおいては単純でオーバーヘッドも少ないメリットがある。

教育用には バブルソート と同様に実装も追いやすいが、入力が整列済みに近いほどステップが少なくなる点が異なる。広い入力では単体ではなく、より高速なアルゴリズムの補助（小区間処理）としての利用が現実的である。