マージ挿入ソート

コンピュータサイエンスにおいて、マージ挿入ソートまたはフォード・ジョンソンアルゴリズムは、 1959年にLRフォード・ジュニアとセルマー・M・ジョンソンによって発表された比較ソートアルゴリズムです。^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}このアルゴリズムは、最悪の場合でも、それまで知られていた最良のアルゴリズムであるバイナリ挿入ソートやマージソートよりも比較回数が少なく、^{[ 1 ]} 20年間、最も比較回数の少ないソートアルゴリズムとして知られていました。^{[ 5 ]}実用的な重要性はありませんが、最小の比較回数でソートを行う問題との関連で理論的な関心を集めています。^{[ 3 ]}同じアルゴリズムがスタニスワフ・トリブラとチェン・ピンによっても独立に発見された可能性があります。^{[ 4 ]}

ランダム化された値の配列をソートするマージ アルゴリズムのアニメーション。

アルゴリズム

マージ挿入ソートは、要素の入力に対して以下のステップを実行する。 ^{[ 6 ]}${\displaystyle X}$ ${\displaystyle n}$

1. の要素を任意に要素のペアにグループ化します。要素の数が奇数の場合は、1 つの要素をペアにしないままにします。${\displaystyle X}$ ${\displaystyle \lfloor n/2\rfloor }$
2. ペアごとに 1 つずつ比較を実行し、各ペアの 2 つの要素のうち大きい方を決定します。${\displaystyle \lfloor n/2\rfloor }$
3. マージ挿入ソートを使用して、各ペアの大きい要素を再帰的にソートし、入力要素の昇順のソートされたシーケンスを作成します。${\displaystyle \lfloor n/2\rfloor }$ ${\displaystyle S}$ ${\displaystyle \lfloor n/2\rfloor }$
4. の最初の最小の要素とペアになった要素の先頭に挿入します。${\displaystyle S}$ ${\displaystyle S}$
5. の残りの要素を、以下に説明する挿入順序に従って、1つずつ に挿入します。 の部分列に対して二分探索（以下に説明する）を用いて、各要素を挿入する位置を決定します。${\displaystyle \lceil n/2\rceil -1}$ ${\displaystyle X\setminus S}$ ${\displaystyle S}$ ${\displaystyle S}$

このアルゴリズムは、探索される部分列の長さが2のべき乗より1小さい場合に、要素を に挿入するために使用されるバイナリ検索が最も効率的である（最悪ケース分析の観点から）という事実を利用するように設計されている。これは、これらの長さでは、探索のすべての結果が互いに同じ数の比較を使用するためである。^{[ 1 ]}これらの長さを生成する挿入順序を選択するには、上記の概要のステップ4の後（残りの要素を挿入する前）のソートされたシーケンスを考慮し、このソートされたシーケンスの 番目の要素を とします。したがって、 ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$

${\displaystyle S=(x_{1},x_{2},x_{3},\dots ),}$

ここで、 の各要素は、まだ挿入されていない要素とペアになっています。（と がペアになっているため、や の要素は存在しません。） が奇数の場合、残りのペアになっていない要素も、 がペアになっている要素のインデックスよりも大きいとして番号付けされます。そして、上記の概要の最後のステップは、以下のステップに展開できます。^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}${\displaystyle x_{i}}$ ${\displaystyle i\geq 3}$ ${\displaystyle y_{i}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle n}$ ${\displaystyle y_{i}}$ ${\displaystyle i}$

• 挿入されていない要素を連続したインデックスを持つグループに分割します。最初のグループには2つの要素とがあり、隣接する2つのグループのサイズの合計は2の累乗の列を形成します。したがって、グループのサイズは2、2、6、10、22、42、…となります。${\displaystyle y_{i}}$ ${\displaystyle y_{3}}$ ${\displaystyle y_{4}}$
• 挿入されていない要素をグループ（小さいインデックスから大きいインデックスへ）順に並べますが、各グループ内では大きいインデックスから小さいインデックスへ並べます。したがって、順序は次のようになります。

${\displaystyle y_{4},y_{3},y_{6},y_{5},y_{12},y_{11},y_{10},y_{9},y_{8},y_{7},y_{22},y_{21}\dots }$

• この順序を使用して、要素を に挿入します。各要素について、 の先頭から まで（ただし は含みません）のバイナリ検索を使用して、 を挿入する場所を決定します。${\displaystyle y_{i}}$ ${\displaystyle S}$ ${\displaystyle y_{i}}$ ${\displaystyle S}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$

分析

マージ挿入ソートが最悪のケースで要素をソートする際に行う比較回数を とします。この比較回数は、以下の3つの項の合計として分解できます。 ${\displaystyle C(n)}$ ${\displaystyle n}$

• ${\displaystyle \lfloor n/2\rfloor }$ アイテムのペア間の比較、
• ${\displaystyle C(\lfloor n/2\rfloor )}$ 再帰呼び出しの比較、および
• 残りの要素を挿入するために使用されるバイナリ挿入の比較がいくつか行われます。

第 3 項では、最初のグループの要素の比較回数の最悪ケースは 2 回です。これは、各要素が最大で長さ 3 の の部分列に挿入されるためです。まず、が 3 要素の部分列 に挿入されます。次に、が 3 要素の部分列 の何らかの順列、または場合によっては 2 要素の部分列 に挿入されます。同様に、2 番目のグループの要素と はそれぞれ、3 回の比較を使用して、最大で長さ 7 の部分列に挿入されます。より一般的には、番目のグループの要素の比較回数の最悪ケースは 回です。これは、各要素が最大で長さ の部分列に挿入されるためです。^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}すべての要素に使用された比較回数を合計し、結果として得られる再帰関係を解くことで、 の値を計算するためにこの分析を使用でき、式^{[ 7 ]が得られます。}${\displaystyle S}$ ${\displaystyle y_{4}}$ ${\displaystyle (x_{1},x_{2},x_{3})}$ ${\displaystyle y_{3}}$ ${\displaystyle (x_{1},x_{2},y_{4})}$ ${\displaystyle (x_{1},x_{2})}$ ${\displaystyle y_{6}}$ ${\displaystyle y_{5}}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle 2^{i+1}-1}$ ${\displaystyle C(n)}$

${\displaystyle C(n)=\sum _{i=1}^{n}\left\lceil \log _{2}{\frac {3i}{4}}\right\rceil \approx n\log _{2}n-1.415n}$

あるいは、閉じた形では、^{[ 8 ]}

${\displaystyle C(n)=n{\biggl \lceil }\log _{2}{\frac {3n}{4}}{\biggr \rceil }-{\biggl \lfloor }{\frac {2^{\lfloor \log _{2}6n\rfloor }}{3}}{\biggr \rfloor }+{\biggl \lfloor }{\frac {\log _{2}6n}{2}}{\biggr \rfloor }.}$

比較の数は^{[ 1 ]}${\displaystyle n=1,2,\dots }$

0、1、3、5、7、10、13、16、19、22、26、30、34、...（OEISのシーケンスA001768）

他の比較ソートとの関係

このアルゴリズムは、再帰呼び出しの前に行う初期比較（任意の項目をペアにして各ペアを比較する）がマージソートの初期比較と同じであるのに対し、再帰呼び出し後に行う比較（二分探索を使用して要素を1つずつソート済みリストに挿入する）は挿入ソートと同じ原理に従うため、マージ挿入ソートと呼ばれます。この意味で、これはマージソートと挿入ソートの両方を組み合わせたハイブリッドアルゴリズムです。^{[ 9 ]}

入力が小さい場合（ まで）、その比較回数は比較ソートの下限に等しくなります。しかし、入力が大きい場合、マージ挿入アルゴリズムによる比較回数はこの下限よりも大きくなります。マージ挿入ソートは、最悪のケースでバイナリ挿入ソートやマージソートによって行われる比較を数えるソート回数よりも少ない比較を実行します。ソート回数は と の間で変動し、上位項は同じですが、下位線形項の定数係数は悪化します。^{[ 1 ]}${\displaystyle n=11}$ ${\displaystyle \lceil \log _{2}n!\rceil \approx n\log _{2}n-1.443n}$ ${\displaystyle n\log _{2}n-0.915n}$ ${\displaystyle n\log _{2}n-n}$

マージ挿入ソートは、の場合にアイテムの比較が最小限に抑えられるソートアルゴリズムであり、 の場合に知られている比較回数が最も少ない。^{[ 10 ] [ 11 ]} 20年間、マージ挿入ソートは、あらゆる入力長に対して知られている比較回数が最も少ないソートアルゴリズムだった。しかし、1979年にGlenn Manacherは、十分に大きな入力に対して、さらに比較回数が少ない別のソートアルゴリズムを発表した。^{[ 3 ] [ 5 ]} すべての に対してソートに必要な比較回数が正確にいくつなのかは不明だが、Manacherのアルゴリズムとその後の記録破りのソートアルゴリズムはすべて、マージ挿入ソートの考え方の修正版を使用している。^{[ 3 ]}${\displaystyle n}$ ${\displaystyle n\leq 22}$ ${\displaystyle n\leq 46}$ ${\displaystyle n}$

参考文献

1. フォード、レスター・R・ジュニア;ジョンソン、セルマー・M. (1959)、 「トーナメント問題」、アメリカ数学月刊、66 : 387–389、doi : 10.2307/2308750、MR0103159 
2. Williamson, Stanley Gill (2002)、「2.31 マージ挿入（Ford–Johnson）」、Combinatorics for Computer Science、Dover books on mathes、Courier Corporation、pp.  66– 68、ISBN 9780486420769
3. Mahmoud, Hosam M. (2011)、「12.3.1 The Ford–Johnson algorithm」、Sorting: A Distribution Theory、Wiley Series in Discrete Mathematics and Optimization、vol. 54、John Wiley & Sons、pp.  286– 288、ISBN 9781118031131
4. Knuth, Donald E. (1998)、「マージ挿入」、The Art of Computer Programming、第3巻：ソートと検索（第2版）、pp.  184– 186
5. Manacher, Glenn K. (1979年7月)、「フォード・ジョンソンソートアルゴリズムは最適ではない」、Journal of the ACM、26 (3): 441– 456、doi : 10.1145/322139.322145
6. Ford & Johnson (1959)によるオリジナルの記述では、要素は降順でソートされていました。ここで示す手順は、 Knuth (1998)の記述に従って、出力を逆順にするものです。結果として得られるアルゴリズムは同じ比較を行いますが、代わりに昇順でソートされます。
7. Knuth (1998)は、この総和公式を A. Hadian の 1960 年の博士論文に帰している。近似公式はFord & Johnson (1959)によって既に与えられていた。
8. ガイ、リチャード・K. ; ノワコウスキー、リチャード・J. (1995年12月)、「月刊未解決問題 1969-1995」、アメリカ数学月刊、102 (10): 921– 926、doi : 10.2307/2975272
9. Knuth (1998) 、p. 184：「これはマージの側面と挿入の側面の両方を含むため、マージ挿入と呼びます。」
10. Peczarski, Marcin (2004)、「最小比較ソートにおける新たな結果」、Algorithmica、40 (2): 133– 145、doi : 10.1007/s00453-004-1100-7、MR 2072769 
11. Peczarski, Marcin (2007)、「Ford-Johnsonアルゴリズムは47要素未満でも依然として無敗」、Information Processing Letters、101 (3): 126– 128、doi : 10.1016/j.ipl.2006.09.001、MR 2287331