アルゴリズムの設計：マージソート(Merge-sort)で学ぶ分割統治法の計算量解析

アルゴリズムの設計とは、与えられた問題を解決するための手続き・手順を考案し、それを正しく効率的に実行できるように組み立てる作業のことです。具体的には、入力（問題のデータ）と出力（結果）との間に、どのようなステップを踏めば解が得られるかを体系的に示し、それを計算機（あるいは人間）が順序通りに実行できるように定義することを指します。

アルゴリズムの「性能」を評価するためには、以下のような観点が重要です。

正しさ：アルゴリズムが意図したとおりに動作し、正しい結果を返すかどうか。
実行時間：アルゴリズムを動かしたときに、、入力サイズ（たとえばデータの個数 n）に対してどの程度の時間がかかるか。
使用メモリ量：アルゴリズムを動かす上で、追加で必要となるメモリがどれくらいか。

このうち、特に実行時間を解析することが、アルゴリズム設計においてきわめて重要で、どれだけ巧妙なアルゴリズムを思いついても、入力サイズが少し大きくなってしまっただけで膨大な時間がかかってしまっては実用的ではありません。入力サイズに応じてそのアルゴリズムの所要時間がどのように変化するかを示すことで、アルゴリズムの効率を比較したり、改良の余地を探ったりできます。これを「アルゴリズム解析」と呼び、アルゴリズム設計のうえで欠かせない考え方の一つです。

: アルゴリズムの解析：RAMモデルと挿入ソートで学ぶ計算量の基本
「アルゴリズム」という言葉は、一言でいえば「何らかの問題を解決するための、手順や処理のしかたの明確な規則」を指す。たとえば「ある数列の中から目的の数を探し出す」「複数のデータを並び替える（ソートする） ...
続きを見る

今回はアルゴリズムを設計するにあたり、大きく二つの考え方を比較しながら進めます。一つは「漸次添加法（incremental method）」と呼ばれる方法で、もう一つは「分割統治法（divide-and-conquer）」と呼ばれる方法です。前者は、すでにソートされている部分配列（あるいは部分的に解が定まっているデータ構造など）に対して、新しい要素を一つずつ挿入していく形でアルゴリズムを構築します。たとえば典型的な例として「挿入ソート（insertion sort）」が挙げられます。

一方、分割統治法は、与えられた問題を複数の小さな部分問題に分割し、それぞれを再帰的に解決した後に解を合わせる手法を指します。大きな問題を直接一気に解くのではなく、ある程度小さな問題に分解してから解くほうが効率的だったり、理解しやすいことが多々あります。「マージソート（merge sort）」は、この分割統治法に基づいて構築される代表的なソートアルゴリズムです。

本解説では、まず分割統治法の考え方を整理し、それを適用した例としてマージソートの仕組みを詳細に解説します。その後、マージソートにおける「マージ（merge）」という操作の内容および解析手法を示し、最終的にマージソート全体の時間計算量をどのように評価するかを説明していきます。これを通じて、分割統治法がどのようにアルゴリズム全体の設計に活かされるのかを理解していただくことを目的とします。

分割統治法とは

分割統治法（divide-and-conquer）は、多くの有用なアルゴリズムの構築に使われる再帰的（recursive）な設計手法です。与えられた問題を解くために、以下の3段階を踏むのが典型的です。

分割(devide)
問題をいくつかの部分問題へと分ける。ここでは、各部分問題のサイズがほぼ同程度になるようにすることが多いです。ソート問題を例に取れば、ソート対象の配列をおよそ半分ずつに分割するのが典型的です。
統治(conqur)
分割した部分問題を再帰的に解く。部分問題のサイズが十分小さい場合は、それを直接あるいは単純な方法（挿入ソートなど）で処理できるため、そこを「再帰の基底段階（base case）」とすることもあります。
結合(combine)
部分問題で得られた解を合成して、元の問題の解へとまとめる。ソート問題の場合は、分割した二つの部分配列をそれぞれソートできたら、それらを適切な手順で一つのソート済み配列に結合します。

分割統治法の重要な点は、元の問題を直接解こうとするのではなく、いくつかの小さな問題に分け、それらを解いて結合するという手順を踏むところにあります。大きな問題を一気に処理するのは難しくても、小さな問題なら容易に対処できることが多い。それを再帰的に繰り返していくことで、最終的に全体の解を得るというのが分割統治法の基本的な考え方です。

このとき、分割や結合の段階でどれだけ時間や労力がかかるかが、アルゴリズム全体の性能を左右します。分割統治法を使う代表的なアルゴリズムには、マージソートのほかにクイックソート、二分探索、最大最小同時探索などがあります。ここではマージソートを例に、具体的な分割統治アルゴリズムの流れを示しながら、解析手法を学んでいきましょう。

マージソートとは

マージソート (merge sort) は、分割統治法に基づいて構成されるソート（整列）アルゴリズムです。入力として配列$A[p \ldots r]$が与えられたとき、以下の手順で要素を昇順（小さい順）に並べ替えます。なお、配列の添字については、テキスト中ではしばしば始まりを 1 と置く例もありますが、ここでは 0 始まりや 1 始まりをそれほど厳密に区別せず、理論上の説明を続けます

マージソートの基本的なステップは次の通りです。

分割(divide):ソートしたい配列$A[p \ldots r]$を、真ん中の位置$q$で二つの部分配列に分割する。
・前半部分$A[p \ldots q]$
・後半部分$A[q+1 \ldots r]$
統治(conquer):分割した２つの部分配列をそれぞれ再帰的にマージソートする。もし部分配列が要素１個以下になったら（つまり$q \geq r$になったら）、それ以上ソートの必要はないので再帰呼び出しを終了する（これが基本段階(base case))。
結合(combine):再帰的にソートされた前半部分と後半部分を「マージ(MERGE)」と呼ばれる手続きで一つの整列済み配列に結合する。

この最終段階の結合（マージ）がマージソートの要となります。マージ操作が効率良く行えると、ソート全体が効率的に機能します。このアルゴリズムは、平均実行時間・最悪実行時間ともに$\Theta(n \log n)$で動作し（後程証明）。非常に重要なソート手法として知られています。

マージアルゴリズム概要

マージソートのコアとなる「マージ (merge)」手続きは、すでにそれぞれソート済みの2つの部分配列を、1つの昇順配列にまとめあげる作業です。

【疑似コード】MERGEアルゴリズム

あらかじめ、左部分配列$A[p . . q]$と右部分配列$A[q+1 . . r]$はそれぞれソートされている（再帰呼び出しによってソート済み）。
左部分配列をL、右部分配列をRという補助配列にコピーする（行３と行４）
二つの配列LとRの先頭要素同士を比較し、小さいほうを元の配列Aに入れていく。これによってAには次々と小さい順に要素が詰め込まれる。
いずれかの配列が先に尽きたら、もう一方に残っている要素をすべてAにコピーする。

こうすることで、もとの位置 p から r までの範囲が昇順に整列されるわけです。
このとき、行 8〜15 のループ（「while i < n_L and j < n_R」）では、左右両方にまだ要素が残っている場合にのみ比較を行い、小さいほうを A に書き込みます。そうしてどちらかが尽きたら、残ったほうをまとめて書き込む（行 18〜25）という仕組みです。

マージアルゴリズム解析

マージの手続き（上記の MERGE）でかかる時間を大まかに見積もります。左右それぞれの配列に要素数を $n_L, n_R$ としたとき，要素の比較・コピーが行われる回数は高々 $n_L+n_R$ 回ほどになります。これは各要素が最終的に必ず A に再配置されるためです。

もし元の配列 $A[p . . r]$ のサイズを $n$ とすると，$n_L+n_R=n$（あるいは $n_L+n_R=n$ か $n-1$ になる場合もあるが，オーダーとしては同じ）。したがって，マージの処理時間は $\Theta(n)$ となります。実際には要素のコピー（行 3,4 ）などもありますが，結局は定数倍の範囲に収まるため，漸近的には $\Theta(n)$ です。

このように，マージは入カサイズに対して線形時間で動作します。マージソートの全体的な計算量解析でポイントになるのは，「分割（divide）」や「統治（conquer）」にかかるコストをどのように数式化するかという点です。

マージソートアルゴリズム

マージソートは、先ほどの分割統治法の各段階を、ソート問題に適用した典型例です。その擬似コードを以下に示します

【疑似コード】MERGE-SORTアルゴリズム

上のように，再帰的に前半部分と後半部分をソートしたあと，最後に MERGE を呼び出すことで，配列 $A[p . . r]$ が整列されます。分割（divide）は「行3」で中央を求める部分に相当し，統治（conquer）は「行4と5」の再帰呼び出し部分，結合（combine）は「行 6」の MERGE 部分です。

このアルゴリズムは，最終的に配列全体 $(p=1, r=n$ とするなど）を呼び出すことで，配列 $A[1 . . n]$ が完全に昇順（小さい順）に並び替えられます。もともと要素数が1以下の場合は（ $p>=r$ で判定），すでにソートが完了しているため何もしません。これが基本段階（base case）となります。

分割統治アルゴリズムの解析について

ここでは、分割統治アルゴリズムの総実行時間を表す漸化式（再帰的な数式）を導き、そこからアルゴリズムの漸近的な時間計算量を求める手法を解説します。

分割統治アルゴリズムでは，問題サイズ $n$ の問題をいくつかの部分問題に分割し（サイズを $n / b$ 程度にする），それらを再帰的に解き，その結果を結合するという流れをたどります。これを式で表すと，しばしば次の形になります（テキストではもう少し具体的な記述もありますが，一般形として）：

$$
T(n)=a T\left(\frac{n}{b}\right)+C(n)
$$

ただし $a$ は部分問題の個数，$\frac{n}{b}$ は各部分問題のサイズ，$C(n)$ は分割や結合のためにかかる時間です。

例えば、マージソートでは、問題を２つに分割($a = 2$)、各部分問題のサイズはほぼ$n/2$、そして結合のステップに$\Theta(n)$時間かかる（マージ処理）ため、次の漸化式が成り立つ

$$
T(n)=2 T\left(\frac{n}{2}\right)+\Theta(n)
$$

ここで、もし問題サイズが十分に小さいとき定数時間 $T(n)=c_1$と定義してもよい。再帰的解析を行う手法にはいくつかあるが、代表的には以下のようなものが知られている。

再帰木を描く方法：問題がどのように分割されるかを木構造で示す
置き換え法：再帰を繰り返して上限・下限を評価する
マスター定理：分割統治アルゴリズムでよく出てくる漸化式を一瞬で分類し、結論を得る定理

最も基本的な方法としては、再帰木や置き換え法を用いて、漸化式を解くことが多い。マージソートの例では、どの手法を使っても結局$T(n)=\Theta(n \log n)$が得られる。

マスター定理について

「マスター定理 (Master Theorem)」という分割統治法特有の解析手法を簡単に触れておきます。これは、次のような漸化式

$$
T(n)=a T\left(\frac{n}{b}\right)+f(n)
$$

（ただし $a \geq 1, b>1$ は定数）について，$f(n)$ の増え方によって $T(n)$ のオーダーがどうなるかを一気に判定する定理です。具体的には 3 つのケースに分けて考えます（以下，必要最小限の説明にとどめます）。

1．Case 1：$f(n)=O\left(n^{\log _b a-\epsilon}\right)$ for some $\epsilon>0$ ．
- $\log _b a$ は再帰の分枝度と深さによる要素数の増え方を示す。
- もし $f(n)$ がそれより低いオーダーなら，再帰呼び出し全体のほうが支配的。結果 $T(n)=\Theta\left(n^{\log _b a}\right)$ 。

2．Case 2：$f(n)=\Theta\left(n^{\log _b a}\right)$ ．
- 分割や結合のコストがちょうど再帰呼び出しと同じオーダーで拮抗している。結果 $T(n)=\Theta\left(n^{\log _b a} \log n\right)$ 。

3．Case 3：$f(n)=\Omega\left(n^{\log _b a+\epsilon}\right)$ for some $\epsilon>0$ ．
- $f(n)$ が再帰呼び出しの合計コストより大きいオーダー。結果 $T(n)=\Theta(f(n))$（ただし技術的条件がある）。

マージソートの場合は $a=2, b=2$ であり， $\log _b a=\log _2 2=1$ 。結合コスト $f(n)$ は $\Theta(n)=\Theta\left(n^{\log _2 2} \cdot n^1\right)$ ，つまりちようど $n^1$ です。よって Case 2 に該当し，$T(n)=\Theta(n \log n)$ となるわけです。

マージソートの解析

マージソートにおける実行時間を解析を、再帰木のイメージを用いて説明します。マージソートは、問題サイズ$n$の配列をちょうど半分に分割するので、漸化式を次のように書けます：

$$
T(n)= \begin{cases}c_1 & \text { if } n \leq 1, \\ 2 T\left(\frac{n}{2}\right)+c_2 n & \text { if } n>1 .\end{cases}
$$

ここで、定数$c_1$は要素数１以下の場合（再帰が底まで行った場合）に要する時間、$c_2 n$マージ（結合）段階でかかる時間を表す単純化したものです。実際にはコピーや比較などで細かい定数が入る可能性がありますが、漸近的なオーダーを求めるためにこのようにまとめます。

この再帰を再帰木のイメージで展開すると次のようになります

レベル0: 問題サイズが $n$
$の配列。ここでは結合にかかるコストが$c_2n$$ かかる（ただし再帰呼び出しを行う前提で、最後のマージとして合計される）。
レベル1: 分割されて問題サイズ
$$n/2$ の部分問題が 2 つ。各部分問題のマージにかかる時間は$c_2(n/2)$$ だが、それが2つあるので、合わせて $c_2n$。
レベル2: さらに分割されて問題サイズ
$$n/4$ の部分問題が 4 つ。各部分問題のマージは$c_2\frac{n}{4}$$ で、4つあるため合計
$$c_2n$$
・・・

部分問題がサイズ1になるまで再帰を続けると，レベル数はだいたい $\log _2 n$（より正確には $\left\lfloor\log _2 n\right\rfloor$ ）程度です。レベルごとに合計 $c_2 n$ のコストがかかり，それが $\log n+1$ レベルほどあるので，総コストは

$$
c_2 n \times\log n + c_1 n
$$

漸近的には$\Theta(n \log n)$となるわけです。

漸化式をもう少し形式的に解く例

$$
T(n)=2 T\left(\frac{n}{2}\right)+c_2 n, \quad T(1)=c_1
$$

とする。仮に $n=2^k$（ 2 のべき乗）と仮定すれば，$k=\log _2 n 。$ 再帰を何段階か展開してみます。

$$
\begin{aligned}
T(n) & =2\left[2 T\left(\frac{n}{4}\right)+c_2 \frac{n}{2}\right]+c_2 n \\
& =4 T\left(\frac{n}{4}\right)+2 c_2 n+c_2 n \\
& =4 T\left(\frac{n}{4}\right)+3 c_2 n .
\end{aligned}
$$

もう1段階：

$$
4 T\left(\frac{n}{4}\right)=4\left(2 T\left(\frac{n}{8}\right)+c_2 \frac{n}{4}\right)=8 T\left(\frac{n}{8}\right)+c_2 n
$$

よって

$$
T(n)=8 T\left(\frac{n}{8}\right)+c_2 n+3 c_2 n=8 T\left(\frac{n}{8}\right)+4 c_2 n .
$$

このように展開を k 回（つまり $\log _2 n$ 回）続けると，最終的に

$$
T(n)=2^k T\left(\frac{n}{2^k}\right)+k c_2 n .
$$

ただし $\frac{n}{2^k}=1$ になるので, $2^k=n 。$ すると

$$
T(n)=n T(1)+\left(\log _2 n\right) c_2 n=n c_1+c_2 n \log _2 n
$$

最終的に

$$
T(n)=c_1 n+c_2 n \log _2 n=\Theta(n \log n) .
$$

これが再帰木の議論を数式でトレースした形になります。この過程で $n$ が 2 のべき乗でない場合でも，漸近的な評価にはほとんど影響せず，同様に $\Theta(n \log n)$ となります。□

ソートアルゴリズムの下限

比較ベースのソートでは「要素を比較して順序を決める」しか手がかりがないため、理論的にはソートにかかる時間が$O(n \log n)$ より速くできないことが示せます（決定木 (decision tree) の議論）。

決定木: ソート対象の比較結果（大小）に応じて木構造をたどるイメージで、最終的に何通りの順列がありうるかを区別しなければならない。
葉の数：全順列$n!$通りをすべて区別する必要がある。
比較1回につき，木の深さが1増える $\rightarrow$ 葉の数 $\geq n!$ を満たすためには深さが $\Omega(\log n!)$ 必要 $\rightarrow$ Stirling の近似などより $\log n!=\Theta(n \log n)$.

よって，比較ベースのソートは少なくとも $\Omega(n \log n)$ の比較が必要というわけです。マージソートは，最悪でも $\Theta(n \log n)$ であるため，この理論的下限に到達しており，効率の良いアルゴリズムと位置づけられます。

他の代表的なアルゴリズムとの比較

クイックソート（quick sort）：分割統治を用いたソートだが，分割（pivot 選択）にランダム性やヒューリスティツクを伴う。平均では $O(n \log n)$ だが最悪 $O\left(n^2\right)$ 。
ヒープソート（heap sort）：ヒープ（優先度付きキューのデータ構造）を用いて最大（最小）要素を取り出しながらソートする手法。これも特定の木構造を使うが，分割統治的な再帰とはやや異なる。最悪 $O(n \log n)$ であるが安定ソートではない。