Day 139-Q4 — Merge Insertion Sort（Ford-Johnsonのアルゴリズム）

2026-08-31 赤色 Master / Phase 8+ ★★★★★★★★★ Jacobsthal数列に基づく挿入順序で比較回数を最小化

問題

$1$ から $N$ までの整数の順列 $A=(A_1,\dots,A_N)$ が与えられる。この順列を Merge Insertion Sort（Ford-Johnsonのアルゴリズム） に従って昇順に整列し、整列後の数列と、その過程で行われた要素同士の比較回数の総数を出力せよ。

Merge Insertion Sort は次の手順で動作する。

  1. 要素を先頭から2個ずつペアにし、各ペアを1回比較して「勝者（大きい方）」と「敗者（小さい方）」に分ける（$N$ が奇数の場合、最後の1個は余り要素として残す）。
  2. 勝者たちだけを取り出し、同じ Merge Insertion Sort を再帰的に適用して昇順に整列する。
  3. 整列済みの勝者列 $b_1<b_2<\dots<b_k$ を骨格（メインチェーン）とし、$b_1$ の敗者 $a_1$（$a_1<b_1$ が保証済み）をチェーンの先頭に挿入して初期チェーン $[a_1,b_1,\dots,b_k]$ を作る。
  4. 残りの敗者 $a_2,\dots,a_k$ と余り要素（あれば）を、Jacobsthal数列（$1,3,5,11,21,43,\dots$）に基づいて決まる順序でチェーンに挿入する。各 $a_i$ の挿入は、チェーン中の $b_i$ の現在位置より前の範囲だけを対象に二分探索で行う。

入力形式

N
A_1 A_2 ... A_N

制約

$1 \le N \le 1000$
$A$ は $1$ から $N$ までの順列

入出力例

入力例1

5
3 1 4 5 2

出力例1

1 2 3 4 5
7

入力例2

1
1

出力例2

1
0

概念図

Jacobsthal数列による挿入順序（降順グループ） Jacobsthal: 1, 3, 5, 11, 21, 43, ... 3, 2 5, 4 11,10,9,8,7,6 各グループ内は降順に挿入、二分探索範囲は b_i の位置まで N=5例: 挿入順序=[3,2] → チェーン [1,3,5] に検算比較=7回で完成 この順序が情報理論的下限 ⌈log2(N!)⌉ に極めて近い比較回数を実現する

ヒント（段階的開示）

ヒント1（方向性）

単純挿入ソートは「1個ずつ、先頭からの整列済み部分に挿入していく」が、これだと要素間の大小関係の情報を最大限には使い切れていない。Merge Insertion Sort は「先にペア比較でおおまかな大小の骨格（勝者チェーン）を作り、敗者たちを適切な順序で挿入する」ことで、比較回数を理論限界（$\lceil\log_2 N!\rceil$）に極めて近づける。

ヒント2（アプローチ）

鍵となるのは2点。(1) 敗者 $a_i$ を挿入する際、$a_i<b_i$ が既知なので、二分探索の範囲を「チェーンの先頭から $b_i$ の直前まで」に絞ってよい。(2) 敗者を挿入する順序を工夫することで、二分探索の対象範囲の長さを「ちょうど二分探索の比較回数が1回増えるタイミング」に合わせられる。この順序を決めるのが Jacobsthal 数列である。

ヒント3（誘導） 
def jacobsthal_order(max_index):
    jac = [1, 3]
    while jac[-1] < max_index:
        jac.append(jac[-1] + 2 * jac[-2])
    order = []
    lo = 1
    for hi in jac[1:]:
        order.extend(range(min(hi, max_index), lo, -1))  # hi から lo+1 まで降順
        lo = hi
    remaining = [i for i in range(2, max_index + 1) if i not in order]
    order.extend(sorted(remaining, reverse=True))
    return order

挿入対象を {2: a_2, 3: a_3, ..., k: a_k, (k+1): 余り要素} のような辞書で持ち、order の順に取り出して挿入すればよい。

模範解答 (Python)

import sys


def ford_johnson_sort(a, cmp_counter):
    n = len(a)
    if n <= 1:
        return list(a)

    pairs = []
    i = 0
    while i + 1 < n:
        cmp_counter[0] += 1
        if a[i] < a[i + 1]:
            pairs.append((a[i + 1], a[i]))
        else:
            pairs.append((a[i], a[i + 1]))
        i += 2
    straggler = a[i] if i < n else None

    winners = [p[0] for p in pairs]
    loser_of = {w: l for w, l in pairs}

    sorted_winners = ford_johnson_sort(winners, cmp_counter)
    k = len(sorted_winners)
    b = sorted_winners
    chain = [loser_of[b[0]]] + list(b)  # [a1, b1, ..., bk]

    insert_map = {}
    for pos in range(1, k):  # b[pos] = b_{pos+1}, その敗者 a_{pos+1}
        insert_map[pos + 1] = loser_of[b[pos]]
    max_index = k
    if straggler is not None:
        insert_map[k + 1] = straggler
        max_index = k + 1

    if max_index >= 2:
        jac = [1, 3]
        while jac[-1] < max_index:
            jac.append(jac[-1] + 2 * jac[-2])
        order = []
        lo = 1
        for hi in jac[1:]:
            order.extend(range(min(hi, max_index), lo, -1))
            lo = hi
        remaining = [i for i in range(2, max_index + 1) if i not in order]
        order.extend(sorted(remaining, reverse=True))
    else:
        order = []

    for pos in order:
        val = insert_map[pos]
        if pos <= k:
            bound_value = b[pos - 1]
            bound_pos = chain.index(bound_value)
        else:
            bound_pos = len(chain)

        lo_, hi_ = 0, bound_pos
        while lo_ < hi_:
            mid = (lo_ + hi_) // 2
            cmp_counter[0] += 1
            if chain[mid] < val:
                lo_ = mid + 1
            else:
                hi_ = mid
        chain.insert(lo_, val)

    return chain


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))

    cmp_counter = [0]
    sorted_a = ford_johnson_sort(a, cmp_counter)

    print(' '.join(map(str, sorted_a)))
    print(cmp_counter[0])


main()

Step-by-Step 解説

1ペア分けで骨格を作る
$N$ 個の要素を2個ずつ比較し、勝者（大きい方）と敗者（小さい方）に分ける。この段階で $\lfloor N/2\rfloor$ 回の比較を使う。勝者だけを再帰的にソートすることで、まず「大まかな順序の骨格（メインチェーン）」を確立する。
2初期チェーンの構築
再帰的に整列済みの勝者列 $b_1<\dots<b_k$ に対し、$b_1$ の敗者 $a_1$ は $a_1<b_1$ が既知なので、比較なしでチェーンの先頭に置ける。これで初期チェーン $[a_1,b_1,\dots,b_k]$（既に昇順に整列済み）が完成する。
3残りの敗者を「範囲を絞った二分探索」で挿入する
$a_i$（$i\ge2$）は $a_i<b_i$ が既知なので、二分探索の対象範囲は「チェーンの先頭から現在の $b_i$ の位置の直前まで」でよい。
4Jacobsthal数列による挿入順序の意味
挿入をインデックス順に行うと、二分探索の比較回数が理論限界より無駄に増える場面がある。Jacobsthal数列の各区間に対応するインデックスを降順に挿入することで、常に「探索範囲の長さがちょうど $2^m-1$ 以下に収まる直前」の状態で二分探索を行えるように調整される。
5検算（入力例1）
$A=(3,1,4,5,2)$: ペア分けで勝者3敗者1、勝者5敗者4、余り2。勝者[3,5]を再帰ソート（1比較）。初期チェーン[1,3,5]。Jacobsthal順序[3,2]で余り2、次に敗者4を挿入。合計比較回数 = 2+1+2+2 = 7。出力例1の7と一致する。

よくあるミス

ミス原因正しい書き方
敗者の挿入をインデックス順（2,3,4,...）に行ってしまう「小さい番号から処理する」という素朴な発想に流されるJacobsthal数列に基づく順序（各グループ内は降順）で挿入しないと、最悪比較回数が理論限界より増える
二分探索の範囲を「チェーン全体」にしてしまうa_i < b_i という既知の情報を使わない対応する b_i の現在のチェーン内位置までに範囲を絞る（chain.index(bound_value)）
余り要素（Nが奇数の場合）の挿入範囲を誤る余り要素には対応する b_i が存在しないことを忘れる余り要素の探索範囲は「チェーン全体」（bound_pos = len(chain)）とする
再帰時に「敗者の対応関係」を見失う勝者の値だけを再帰に渡し、どの敗者とペアだったか追跡しないloser_of のような辞書（勝者の値→敗者の値）を各再帰レベルで保持する
N<=1 や N=2 の基底ケースを一般ロジックと同じコードで無理に処理しようとして例外を出す再帰の終端条件を明示的に分けていないn <= 1 を明示的な基底ケースとして早期リターンする

次のステップ

  • 発展: 出力される比較回数が、既知の Ford-Johnson の最小比較回数の値（$N=1,\dots,20$ 程度の小さな $N$ に対する公表値）と一致することを、複数のランダムな順列に対して検証せよ。
  • 発展2: 情報理論的下限 $\lceil\log_2 N!\rceil$ を計算する関数を実装し、本問の出力する比較回数との差を $N=1$ から $1000$ まで調べてグラフ化せよ。

自己評価

自分の回答

気づき・メモ