挿入ソート

手札を並べるように、1つの値をキーとして保持し、それより大きい値を右へずらして空いた位置に挿入します。

再生・ステップ実行・スライダーで操作できます。下段に浮かぶピンク色の棒が保持中のキーです。

最良O(n)

平均O(n²)

最悪O(n²)

追加領域O(1)

安定はい

得意な入力ほぼ整列済み

ほぼ整列済みの配列に強い

キーより大きい値だけを動かすので、ほぼ整列済みなら移動が少なくO(n)に近づきます。「ほぼ整列済み」と「逆順」を比べてください。小さな区間にも効率的で、多くの実用的なソートの一部として使われています。

同じ値をキーより右へ移動させないため、元の順序が保たれます。

演習

移動回数も転倒数と一致します。値が1つずつ到着する場合は bisect.insortで挿入位置を探せますが、Pythonのリストへの挿入自体はO(n)で、全体はO(n²)です。大量のデータでは別のデータ構造、例えばヒープなどを検討します。