挿入ソート (Insertion Sort)

手札を整えるように各要素を整列済み区間へ挿入するソートを棒アニメーションで確認。ほぼ整列済みデータでO(n)に近い理由が分かります。

アルゴリズム

配列

サイズ48
比較中交換/書込ピボット/基準読み整列確定
速度50×

比較

0

交換/書込

0

ステップ

0/1,373

読み

0

補助メモリ

0

再帰の深さ

1/1

速度を落として「1ステップ」で疑似コードのハイライトと棒の色を見比べてみてください。

疑似コード

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

計算量

最良O(n)
平均O(n²)
最悪O(n²)
空間O(1)
安定○

挿入ソートは2番目の要素から1つずつ取り出し(key)、左の整列済み区間で自分より大きい値を後ろへずらして空いた場所へ挿入します — トランプの手札整理と同じ動きです。

最悪はO(n²)ですが、ほぼ整列済みなら各要素の移動が少なく実質O(n)に近づきます。Timsort等のハイブリッドソートが短い区間で挿入ソートに切り替える理由です。安定・インプレースソートです。 ソート可視化

よくある質問

挿入ソートが速いのはどんな時?
配列が小さい(目安50要素以下)か、ほぼ整列済みの時です。実際のライブラリソートが短い区間で採用する理由でもあります。
安定ソートですか?
はい。keyより大きい値だけをずらすため同値の順序は保たれます。

他のアルゴリズム