初学者によるFord–Johnson（Merge–insertion）アルゴリズム 解説

必要があってFord–Johnsonアルゴリズムについて学びました。
Ford–Johnsonアルゴリズム（または Merge–insertion sort）について、なるべく分かりやすく、自分なりに、その背景やアルゴリズム構造・特徴を説明します。
初学者が。
初学者が。
以下の解説にそこまで大きく責任持てませんよという意味です。間違ってたらぜひ教えていただきたいです。お願いします！！

1. 背景と概要

「なるべく比較回数を減らしてソートする」ことを目標としたとき、Ford–Johnsonアルゴリズムは優秀です。

1.1 なぜ比較回数を減らすソートが重要なのか？

• ソートアルゴリズムを評価する尺度の一つに、比較演算の回数があります。
• プログラムなどで実装するときは、速度や計算量が重視されると思いますが、その因子として比較回数も含まれます。
• ※比較回数が少ない＝早いor計算量が少ない ではないです。比較以外の部分も速度に大きく関係してるらしいです。
• 比較にコストがかかる場合は望ましいアルゴリズムであると言えます。具体例では、テニスの全選手の順位を最小回数の試合で決めたい時の例がよく紹介されるらしいです。

1.2 Ford–Johnsonアルゴリズム（Merge–insertion sort）とは

• 1959年に、L. R. Ford Jr. と S. M. Johnson によって提案されました。
• 比較回数の最悪ケースで、従来のマージソートやバイナリ挿入ソートよりも少ない比較回数でソートできることが示されています。
• 実装が非常に複雑で、大規模プログラムで使用されることは少ないものの、理論的興味や最適比較回数にどれだけ近づけるかという点で非常に重要なアルゴリズムらしいです。

2. アルゴリズムの要旨

Ford–Johnsonアルゴリズムは、大きく以下2つの手法を組み合わせたハイブリッド型です。
以下に発想を説明しますが、具体的な手順は別途説明します。

1. Merge的な発想:
   入力シーケンスをペアに分割し、各ペアで大きい要素 (winner) を集める。
   これを再帰的に行い、要素1になるまで繰り返します。
   マージソートのディバイド&コンカーですね。

2. Insertion的な発想:
   ペアで余った小さい要素 (loser)たちを、既にソート済みのwinners列に対して挿入していく。
   ただし、その挿入順序が特殊で、「2, 2, 6, 10, 22, …」など一定パターンのグループ分けを行い、グループごとに「大きいインデックスから先に挿入」するという独特のルールがあります。かなりだるいルールですが、挿入ではあります。

この2つの手法を統合することで、比較回数のばらつきを抑え、最悪ケースでもなるべく少ない比較回数に収められる、というのがFord–Johnsonアルゴリズムの核心です。

3. 手順の全体像

あらかじめ言っておきますとかなり字面ではわかりづらいです。です。ですが、字面で整理するだけしておきましょう。

3.1 ペア分け

1. 要素をペアに分ける
   • 配列（リスト）の要素を2個ずつ取ってペア化し、それぞれを比較。
   • 大きいほう (winner) と 小さいほう (loser) を決定します。多くの説明では、winnerはx_i、loserはy_iの列で表現されてました。
   • 元の配列の要素数が奇数の場合、端の1要素はloserに組み入れます。
2. winnersの再帰ソート
   • winners だけを取り出し、同じFord–Johnsonアルゴリズムを再帰的に呼び出してソートする。
3. 特殊ペアの処理
   • アルゴリズムの説明によっては、「最初のペア」から出た最小要素を特別扱いする。
   • これにより、後述する「x_1, x_2 の対応する y_1, y_2 が存在しない」状況を作るなど、細かな定義がなされています。

3.2 グループ分けによるinsertion

1. losers（未挿入要素）の回収
   • ペアで小さいほう（loser）を「未挿入要素」として一時保存しておく。
2. 再帰が終わったソート済みwinnersに対して、losersを挿入
   • losersは、「2,2,6,10,22,42,…」というサイズのグループに区切る。
   • グループごとに、大きいインデックスの要素からwinnersへ挿入していく。
3. 挿入時の範囲は挿入するloserと対になっているwinnerまで
   • loserと対になるwinnerより前の範囲に二分探索をかけて適切な位置に挿入する。
   • これによって、最悪比較回数を一定に抑えられるよう工夫されています。

4. 擬似コードのサンプル

以下は、抽象度の高いサンプルコードです。実際の実装ではより煩雑な処理が必要になりますが、
流れをつかむうえで参考にしてください。

// 擬似コード
function FordJohnsonSort(A):
    n = A.size()

    if n <= 1:
        return
    // 奇数の場合は末尾 extra を除き、偶数にしてからソートして後で挿入
    if n is odd:
        extra = A.last()
        A.pop_back()
        FordJohnsonSort(A)
        binaryInsert(A, extra)
        return

    // 1. ペア分け
    // 最初のペアは特別扱い
    if A[0] < A[1]:
        winners.push(A[1])
        specialLoser = A[0]
    else:
        winners.push(A[0])
        specialLoser = A[1]

    // 残りのペア
    for i in range(2, n, step=2):
        if A[i] < A[i+1]:
            winners.push(A[i+1])
            losers.push((A[i+1], A[i])) // (threshold, loser)
        else:
            winners.push(A[i])
            losers.push((A[i], A[i+1]))

    // 2. winners の再帰ソート
    FordJohnsonSort(winners)

    // 3. specialLoser を先頭に入れる
    winners.insert(0, specialLoser)

    // 4. losers のグループ挿入
    // グループサイズを 2,2,6,10,22,... と並べ、各グループを後ろ→前の順で挿入
    insertionOrder = buildInsertionOrder(losers.size()) // [4,3,2,1,0,...]など計算
    for index in insertionOrder:
        threshold = losers[index].threshold
        val       = losers[index].loser
        // threshold の位置より前に二分探索をかけて val を挿入
        winners.insertAtBinarySearch(val, upTo=threshold)

    // 5. A を winners に置き換え
    A = winners

• binaryInsert: 二分探索により要素を挿入する関数（範囲が明示的に制限される場合もある）。
• buildInsertionOrder: losersを指定したグループサイズ(2,2,6,10,22,…)で分割し、グループ内を逆順に並べるためのインデックス配列を生成する関数。
• 細部は省略していますが、実際には“特別ペア”の処理や要素数が奇数のときの取り扱いなど、実装上の工夫が必要です。細かいルールがあってめんどくさいですよね..。

5. 難しいポイント

1. “ペア分け”と“再帰”の分離

   • Ford–Johnsonでは、まずペア分けで勝ち抜いた大きい方の要素だけを再帰的にソートします。
   • その後、小さい方（losers）は再帰から戻ってきたソート済み列 へ追加挿入する形です。
   • 一括で最後にまとめるのではなく、各再帰レベルごとに“未挿入要素を挿入する”という流れになっています。

2. グループサイズの決め方

   • losersを挿入するときの「2, 2, 6, 10, 22, 42…」というグループサイズは、最悪比較回数をなるべく均一化するための設計です。
   • 一見突拍子もない数字列に見えますが、「隣接する2グループの合計が2の冪数になる」ように調整されています。
   • これによって、挿入する際の二分探索範囲が常に (2^k - 1) 個になるように配慮し、比較数を平準化しているのです。
     ↑正直、マジで理解が追いつかないです

3. 特別ペア ((x_1, x_2)) の存在

   • 「最初のペアの小さい要素は別途先頭に挿入する」という処理。
   • これによりlosersのindexが3から始まる説明が多くて、訳わからんがちです。

4. 実装が非常に煩雑

   • 比較回数を理論的最小に近づけるために、細かいルールがたくさんある。
   • ペア分けを繰り返して要素1になったかと思ったら、コマ戻しと挿入の連続が始まる...しかも挿入には特殊ルールが...。諦めるチャンスがいっぱいあります。

6. 私が理解するうえで苦戦したポイント

実際に私がFord–Johnsonアルゴリズムを学ぶ過程で混乱しがちだったポイントを説明させてください。僕はこの誤解が誤解だったと思ってますが、普通に僕の解釈ミスの可能性もあります。頼むから誤解であってください。

未挿入要素（losers）の挿入タイミング

• 誤解: 「一通り再帰が終わったあとで losers をまとめて挿入すればいいのでは？」
• 実際: Ford–Johnsonでは、「ペア分け → winnersを再帰ソート → losersをその段階で挿入」という手順を各再帰段階で完結させます。
• これは、losers と対になる winners のインデックス（threshold）を意識する必要があるためです。
  • ペアで生まれた loser は、そのペアでの大きいほう(winner)より常に小さいので、“どの winner に対応していたか”という情報が挿入時の探索範囲を決めます。
  • 再帰の下位段階でも同じ仕組みを繰り返すことで、部分問題ごとに正しい順序を保証します。

7. まとめ

• Ford–Johnsonアルゴリズム（Merge–insertion sort）は、
  1. ペア分けして大きい要素だけを再帰的にソート
  2. 小さい要素を特殊ルール（グループ分け & 逆順挿入）で順次挿入
     という2ステップを、各再帰段階ごとに繰り返すハイブリッドソートです。
• 比較回数の削減を理論的に追求する文脈で重要視されてきた歴史があり、特に要素数が小さい場合は最適回数に一致したり、大きい場合でも従来のソートより少ない比較回数が得られます。
• ただし実装が複雑で、実運用でしばしば用いられるわけではないらしいことには注意してください。

ふぅ。難しかったです。。
検索しても基本英語＆あんまりよくわかんない説明 だったので、後続の参考資料が一つでも増えたらなと思います。