比較回数を最小化する賢いソート
マージ挿入ソート（Ford-Johnsonアルゴリズム）は、「比較」という操作を極限まで減らすことに特化した高度なアルゴリズムです。このシミュレーターで、その複雑な手順をステップごとに解き明かしていきましょう。
アルゴリズムの可視化
処理ステップ
最適化の鍵：ヤコブスタール数
なぜこのアルゴリズムは効率的なのでしょうか？その秘密は、保留要素（Pend）をメインチェーンに挿入する**順番**にあります。この順番を決めているのが「ヤコブスタール数」です。
ヤコブスタール数とは？
前の2つの数から次の数を計算する数列です (J(n) = J(n-1) + 2*J(n-2))。
どのように活用されるのか？
Ford-Johnsonアルゴリズムは、この数列から導き出される**挿入順序** `(3, 2, 5, 4, 11, 10, ...)` を使います。 この順番で保留要素を挿入することで、二分探索を行う対象（メインチェーン）のサイズが、**可能な限り小さい状態**に保たれます。 例えば、保留要素の3番目(`a₃`)を先に挿入し、次に2番目(`a₂`)を挿入します。`a₃`を挿入する際の探索範囲は`b₃`までですが、`a₂`を挿入する際の探索範囲はより小さい`b₂`までで済みます。 このように、**探索範囲が大きくなる前に、より小さい範囲で探索できるものを先に片付けてしまう**のが、ヤコブスタール数を使った最適化の本質です。これにより、全体の比較回数が最小限に抑えられるのです。