Ford-Johnsonアルゴリズム（Merge-Insertion Sort）は、比較回数を数学的な極限まで削減するために設計された、高度に最適化されたソートアルゴリズムです。
本稿では、その仕組みを20個の要素を用いた具体例とともに解説します。
1. アルゴリズムの三原則
- 比較の節約: 要素をペアにして「勝者」だけを先に並べることで、全体の構造を素早く決定する。
- 構造の維持: 「敗者」は常に、自分を負かした「勝者」との関係性を保持する。
- 効率的挿入: ヤコブスタール数列を用い、二分探索の効率が最大となるタイミングで要素を挿入する。
2. 20要素による完全シミュレーション
以下の20個の乱数をソートする過程を追います。
[13, 7, 20, 1, 15, 4, 11, 2, 18, 5, 9, 14, 17, 3, 6, 12, 10, 19, 8, 16]
ステップ1：ペアリング
要素を2個ずつのペアにし、大きい方を「勝者」、小さい方を「敗者」に分けます。
| ペア | (13, 7) | (20, 1) | (15, 4) | (11, 2) | (18, 5) | (9, 14) | (17, 3) | (6, 12) | (10, 19) | (8, 16) |
|---|---|---|---|---|---|---|---|---|---|---|
| 勝者 | 13 | 20 | 15 | 11 | 18 | 14 | 17 | 12 | 19 | 16 |
| 敗者 | 7 | 1 | 4 | 2 | 5 | 9 | 3 | 6 | 10 | 8 |
ステップ2：勝者の再帰的ソート
10個の勝者たちだけを抽出し、再び同じ手順でソートします。
最終的に、勝者たちは以下の順番に並びます。
勝者列（基幹列）:
[13, 20, 15, 11, 18, 14, 17, 12, 19, 16]
ソート済み勝者列（基幹列）:
[11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
ステップ3：関係性の再構築
勝者たちの背後には、ステップ1で負けた敗者たちが紐付いています。
- (11-2) / (12-6) / (13-7) / (14-9) / (15-4) / (16-8) / (17-3) / (18-5) / (19-10) / (20-1)
敗者列（挿入待ちグループ）:
[2, 6, 7, 9, 4, 8, 3, 5, 10, 1]
ここで、ソート済みの勝者列を 基幹列（Main Chain）、挿入を待っている敗者たちを 挿入待ちグループ と呼びます。
3. ヤコブスタール数列による「魔法の挿入」
ここからがこのアルゴリズムの真骨頂です。残りの敗者10人を基幹列に挿入していきますが、「前から順番に」入れることはしません。
なぜ「0, 2, 1, 4, 3...」の順なのか？
二分探索では、探索対象の要素数が $2^n - 1$ （3, 7, 15...）個である時、最も効率的に場所を特定できます。
ヤコブスタール数列（$J_n$）を利用して挿入の「区切り」を決め、
その区切りの端から 逆順 に挿入することで、常に「自分より前にいる要素数」を理想的な数に保つのです。
挿入のスケジュール
敗者たちを $L_1, L_2, ..., L_{10}$ とします（$L_n$ は勝者 $W_n$ に負けた要素）。
-
最初の無条件挿入: $L_1$ (2) を先頭に配置。
- 基幹列:
[2, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
- 基幹列:
-
第1ブロック (J3=3まで): $L_3, L_2$ の順に挿入。
- 7 を挿入、次に 6 を挿入。
- 基幹列:
[2, 6, 7, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
-
第2ブロック (J4=5まで): $L_5, L_4$ の順に挿入。
- 4 を挿入、次に 9 を挿入。
- 基幹列:
[2, 4, 6, 7, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
-
第3ブロック (J5=11まで): $L_{10}, L_9, L_8, L_7, L_6$ の順に挿入。
- 1, 10, 5, 3, 8 の順に挿入。
- 基幹列:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
- 余りがある場合(配列のサイズ % 2 != 0)は、最後に2分探索で挿入
視覚的な動き
挿入待ち順序:
[L1] -> [L3, L2] -> [L5, L4] -> [L10, L9, L8, L7, L6]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
(2) (7, 6) (4, 9) (1, 10, 5, 3, 8)
この「戻りながら挿入する」動きによって、後に挿入される要素ほど、すでに長くなった基幹列を相手にしながらも、
二分探索の比較回数が「壁（$2^n-1$）」を超えないように工夫されているのです。
二分探索の「探索範囲」の最適化
敗者を基幹列に挿入する際、多くの実装例で std::lower_bound(arr.begin(), arr.end(), val) のように列全体を探索してしまいますが、厳密にはこれは無駄な比較を生んでいます。
例えば、敗者 4 を挿入する時、ペアだった勝者 15 はすでに基幹列の中にいます。
敗者は絶対に勝者より小さいため、4 が入る可能性があるのは基幹列の先頭から、勝者 15 がいる位置までに限定されます。勝者より右側を探す必要は全くありません。
【理論上の最強実装】
// ペアだった勝者の現在位置を特定し、そこを上限（end）として二分探索する
std::vector<int>::iterator winner_pos = /* 勝者の現在位置 */;
std::lower_bound(arr.begin(), winner_pos, val);
4. 段階別のまとめ
フェーズ1：ペアの構築
- 全要素を戦わせ、強者と弱者のペアを作る。
- この時点で、全体の比較回数を一気に半分に抑え込む。
フェーズ2：再帰による序列決定
- 強者たちを並べることで、ソートの「背骨」を作る。
- 小さな問題に分解して解く（分割統治）ことで、効率を維持する。
フェーズ3：戦略的挿入
- ヤコブスタール数列に基づき、ブロックごとに逆順で挿入。
- 二分探索の「最悪ケース」を極限まで回避する。
5. 結論
Ford-Johnsonアルゴリズムは、単なるマージと挿入の組み合わせではありません。
「どの要素を、どのタイミングで、どの範囲に挿入すれば、最も情報の価値が高まるか」
を数学的に計算し尽くした、情報の不確実性を最小化する戦略なのです。