ALDS1_5_B:

バブルソートなどの $O(n^2)$ の初等的なアルゴリズムは大きなサイズの配列に対しては実用的ではありません。マージソートは、大きなサイズのデータに対応することのできる高等的なアルゴリズムのひとつです。

マージソートは以下の手順に基づく分割統治法（Divide and Conquer）のアルゴリズムです。

1. 与えられた問題を部分問題に分割する
2. 部分問題を再帰的に解く
3. 得られた部分問題の解を統合して、元の問題を解く

マージソートは次のようなアルゴリズムになります：

• 配列全体を対象として mergeSort を行う。
• mergeSort は次の通り：
  1. 指定された $n$ 個の要素を含む部分配列をそれぞれ $n/2$ 個の要素を含む２つの部分配列に「分割」する。（Divide）
  2. その２つの部分配列をそれぞれ mergeSort でソートする。（Solve）
  3. 得られた２つのソート済み部分配列を merge により「統合」する。（Conquer）
  

マージソートは、既にソート済みの２つの配列をマージ（合併）するアルゴリズム merge が基礎になっています。それぞれ n1 、 n2 個の整数が格納された配列 L と R を配列 A にマージすることを考えます。 L と R はそれぞれ昇順に整列されているものとし、 L と R のすべての要素をそれらが昇順になるように A にコピーします。

ここで重要なことは、 L と R を連結した後、通常のソートアルゴリズムを適用するのではなく、それぞれソート済みということを利用し、計算効率が $O(n1 + n2)$ となるようなマージのアルゴリズムにすることです。例えば、２つの整列済み配列 L = {1, 5} と R = {2, 4, 8} をマージすると以下のようになります。

merge では、L と R のそれぞれの末尾に番兵としてどの要素よりも大きな値を配置することで実装を簡略化することができます。L、R の要素を比較していく過程で、ある要素と番兵を比べる局面がありますが、番兵として大きな値を設定し、比較する回数を n1 + n2 （right − left）とすれば、番兵どうしが比較されることも、ループ変数 i、j がそれぞれ n1、n2 を超えることもありません。

mergeSort を詳しく確認します。mergeSort は配列 A とその配列の部分配列の範囲を表す変数 left と right を引数とします。次の図のように、left は部分配列の先頭の要素、right は部分配列の末尾+1 の要素を指します。

例えば、配列 $\{9, 6, 7, 2, 5, 1, 8, 4, 2\}$ に対して MergeSort を行うと以下のようになります。

下に向かう矢印が分割、上に向かう矢印が統治を表し、矢印の数字が処理の順番を示しています。mergeSort で分割、merge で統治していきます。

mergeSort は部分配列の要素数が 1 以下のときは何もせず終了します。部分配列の中央の位置 mid を計算し、部分配列の前半部分は left から mid （ mid は含まない）、後半部分は mid から right （ right は含まない）とし、前半部分、後半部分それぞれに mergeSort を行います。

Merge の処理の直前には、すでに２つの部分配列はソート済みになっているので、$O(n1 + n2)$ のアルゴリズムを適用することができます。

上図の配列 $\{9, 6, 7, 2, 5, 1, 8, 4, 2\}$　では 9 個のデータを１個になるまで分割すると、$9 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 1$ の４回の分割が必要で、階層が５つになります（8 個のデータの場合は $8 \rightarrow 4 \rightarrow 2 \rightarrow 1$ の４階層）。一般的に $n$ 個のデータの場合はおおよそ $log_2 n$ 回の分割が行われます。各階層ごとに行われるすべての Merge の総計算量は $O(n)$ になるので、マージソートの計算量は $O(n\; log\; n )$ となります。

マージソートは離れた要素同士を比較しますが直接交換することはありません。前半と後半のソート済み配列をマージする処理で、対象となる２つの要素が同じ場合は常に前半の部分配列の要素を優先させれば、同じ値の要素の順番が入れ替わることはないので、マージソートは安定なソートアルゴリズムです。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。