整列済み部分を一つ増やす
挿入ソートは、配列の左側を整列済みの領域として維持し、その直後の要素を適切な位置へ入れます。挿入する値を一時的に退避し、それより大きい要素を右へずらし、空いた場所へ値を置きます。外側の反復が位置iへ来た時点で、区間[0,i)は整列している、という不変条件が説明の軸です。右側は未整列のままで構わず、全体から最小値を毎回探す必要もありません。比較する値と移動するレコードを混同しないことが大切です。
5、2、4、2を追う
[5,2,4,2]では、最初の2を退避して5を一つ右へずらすと[2,5,4,2]になります。次の4は5だけを越えて[2,4,5,2]へ入り、最後の2は5と4を越えて[2,2,4,5]へ入ります。同じ値の2を元の位置で区別しておくと、厳密に大きい要素だけをずらす場合は最初の2が先に残ることが分かります。等しい要素まで越えてしまう条件では、この安定性は保たれません。値だけでなく出現順も書いて追跡しましょう。
反転数が移動回数を決める
反転とは、先にある値の方が後の値より大きい組です。隣接する要素をずらす実装では、挿入による移動は反転を解消する操作に対応します。反転数をIとすると、定数時間比較の下で処理量はO(n+I)と説明でき、既に整列済みなら線形時間です。逆順の異なるn要素にはn(n−1)/2組の反転があるため二次時間になります。どちらも最悪O(n²)という一言で済ませると、ほぼ整列した小区間で使いやすい理由が見えなくなります。
二分探索を足しても移動は残る
挿入位置を二分探索すれば比較回数は減らせますが、連続配列の途中へ要素を入れる移動は消えません。そのため二分挿入ソートを一般のO(n log n)時間の整列とみなすのは誤りです。通常の実装の追加領域はO(1)ですが、大きなレコードのコピーや高価な比較では費用の内訳が変わります。空配列、要素一つ、同じキーが並ぶ入力を試し、比較関数が整合した順序を与えることも確認します。巨大で乱れた入力には別の整列法が適しています。