22.2 マージソート

格式高いアルゴリズムの教科書はソートが情報科学で基礎的な役割を果たす重要な問題だと主張する。そういった教科書は、Hanoi の塔で休むことなく円盤を移動させ続ける僧侶の人生が輝いて見えるほどの長い時間をかけて様々なソートアルゴリズムに関する話題で読者を痛めつける。本書では有名なソートアルゴリズムを一つだけ紹介する: マージソート (merge sort) である。このアルゴリズムを解析すると、本書で初めて目にする形の再帰方程式が現れる。

マージソートは次のように動作する。\(n\) 個の数字が並んだリストが入力され、そのリストに含まれる数字を非減少の順序で並び替えたリストが出力となる。処理は二つの場合に分かれる:

入力のリストに数字が一つだけ含まれるなら、ソートは必要ないので、何もせず入力をそのまま出力する。
それ以外の、入力のリストに二つ以上の数字が含まれる場合は、リストを二等分して前半部分と後半部分を再帰的にソートする。その後、二つのソート済みリストをマージ統合して一つの完全なソート済みリストとする。

例を使って動作を確認しよう。次のリストをソートしたいとする:

\[ (10,\ 7,\ 23,\ 5,\ 2,\ 8,\ 6,\ 9) \]

このリストには二つ以上の数字が含まれるので、まず前半部分 \((10, 7, 23, 5)\) と後半部分 \((2, 8, 6, 9)\) が再帰的にソートされる。この結果は \((5, 7, 10, 23)\) と \((2, 6, 8, 9)\) である。最後に、この二つのソート済みリストがマージされる。マージの様子を次に示す。下線は出力に追加される数字を表す。

\[ \def\arraystretch{1.35}\begin{array}{rrr} \text{前半部分} & \text{後半部分} & \text{出力} \\ 5, 7, 10, 23 & \underline{2}, 6, 8, 9 & \\ \underline{5}, 7, 10, 23 & 6, 8, 9 & 2 \\ 7, 10, 23 & \underline{6}, 8, 9 & 2, 5 \\ \underline{7}, 10, 23 & 8, 9 & 2, 5, 6 \\ 10, 23 & \underline{8}, 9 & 2, 5, 6, 7 \\ 10, 23 & \underline{9} & 2, 5, 6, 7, 8 \\ \underline{10}, \underline{23} & & 2, 5, 6, 7, 8, 9, 10, 23 \end{array} \]

二つのリストの先頭要素は \(5\) と \(2\) なので、最初に \(2\) を出力する。この \(2\) を後半部分のリストから取り除くと、二つのリストの先頭要素は \(5\) と \(6\) になる。そのため次は \(5\) が出力される。この処理を続けると、いずれどちらかのリストが空になる。その後は要素が残っているリストの要素を全て出力に付け足せば、ソートされた完全なリストが完成する。

22.2.1 再帰方程式を見つける

ソートアルゴリズムに対する伝統的な質問として「\(n\) 個の要素をソートするとき、最大で何回の比較が実行されるか？」がある。この質問の答えは実行時間の推定値となる。マージソートでは、この値を再帰方程式で表せる。

以降では \(n\) が \(2\) の冪だと仮定する。このとき、再帰的に呼び出されるものを含む全てのマージソートにおいて二つに分割されたリストの要素数は同じになる。\(n\) 要素のリストをマージソートしたとき実行される比較の最大回数を \(T_{n}\) とする。\(T_{n}\) に関して次のことが分かる:

リストの要素が \(1\) 個だけなら、比較は実行されない。つまり \(T_{1} = 0\) が成り立つ。
そうでないなら、\(T_{n}\) は「前半部分のソートで実行される比較の最大回数」と「後半部分のソートで実行される比較の最大回数」と「マージ処理で実行される比較の最大回数」の和である。最初の二つの値は \(T_{n}\) の定義より \(T_{n/2}\) に等しい。また、最後の値は \(n - 1\) に等しい。なぜなら、マージ処理では \(1\) 回の比較ごとに出力されるリストの要素が \(1\) 個決定し、比較が最も多くなるとき最後に残るリストの要素数は \(1\) となるためである。出力は \(n\) 要素のリストなので、マージ処理で実行される比較は最大で \(n - 1\) 回だと分かる。

よって、\(n\) 要素のリストをマージソートするときに実行される比較の最大回数 \(T_{n}\) は次の再帰方程式を満たす:

\[ \begin{aligned} T_{1} &= 0 \\ T_{n} &= 2 T_{n/2} + n - 1 \qquad (n \geq 2,\ \text{\(n\) は \(2\) の冪}) \end{aligned} \]

この再帰方程式によって比較の最大回数は完全に決定されるものの、この表現が有用とは言えない: 閉形式の式で表した方がずっと扱いやすい。閉形式の式を得るには、再帰的を解かなければならない。

22.2.2 再帰方程式を解く

上述の再帰方程式に推測検証の方法を適用してみよう。\(T_{n}\) の最初の数項の値は次のようになる:

\[ \begin{aligned} T_{1} &= 0 \\ T_{2} &= 2 T_{1} + 2 - 1 = 1 \\ T_{4} &= 2 T_{2} + 4 - 1 = 5 \\ T_{8} &= 2 T_{4} + 8 - 1 = 17 \\ T_{16} &= 2 T_{8} + 16 - 1 = 49 \\ \end{aligned} \]

困った！明らかなパターンが無いので、再帰方程式の解を表す閉形式の式を推測するのは難しそうだ。では定義代入の方法を試してみよう。

ステップ 1: パターンが現れるまで定義の代入を繰り返す

まず、再帰方程式の定義を代入して整理することを繰り返し、パターンが現れるかどうかを確認する:

\[ \begin{align*} T_{n} &= 2 T_{n/2} + n - 1 && \\ &= 2 (2 T_{n/4} + n/2 - 1) + (n - 1) && (\text{代入}) \\ &= 4 T_{n/4} + (n - 2) + (n - 1) && (\text{整理}) \\ &= 4 (2 T_{n/8} + n/4 - 1) + (n - 2) + (n - 1) && (\text{代入}) \\ &= 8 T_{n/8} + (n - 4) + (n - 2) + (n - 1) && (\text{整理}) \\ &= 8 (2 T_{n/16} + n/8 - 1) + (n - 4) + (n - 2) + (n - 1) && (\text{代入}) \\ &= 16 T_{n/16} + (n - 8) + (n - 4) + (n - 2) + (n - 1) && (\text{整理}) \end{align*} \]

パターンが現れた。一般化すると、次の等式が成り立ちそうに思える:

\[ \begin{aligned} T_{n} &= 2^{k} T_{n/2^{k}} + (n - 2^{k-1}) + (n - 2^{k-2}) + \cdots + (n - 2^{0}) \\ &= 2^{k} T_{n/2^{k}} + kn - 2^{k-1} - 2^{k-2} - \cdots - 2^{0} \\ &= 2^{k} T_{n/2^{k}} + kn - 2^{k} + 1 \end{aligned} \]

二行目の式変形では \(k\) 個の \(n\) をまとめて \(kn\) にしている。三行目の式変形では幾何級数を閉形式の式に変形している。

ステップ 2: パターンの正しさを検証する

続いて、定義の代入と整理をもう一度使ってパターンの正しさを検証する。見つけたパターンが間違っていれば、このステップで誤りが判明する。

\[ \begin{aligned} 2^{k} T_{n/2^{k}} + kn - 2^{k} + 1 &= 2^{k} (2 T_{n/2^{k+1}} + n/2^{k} - 1) + kn - 2^{k} + 1 && (\text{代入}) \\ &= 2^{k+1} T_{n/2^{k+1}} + (k + 1) n - 2^{k+1} + 1 && (\text{整理}) \end{aligned} \]

最後の式は最初の式に含まれる \(k\) を \(k + 1\) に置き換えた式なので、この式変形は \(k \geq 1\) に対する等式の正しさを示す数学的帰納法による証明の帰納ステップにちょうど対応する。

ステップ 3: 既知の値を使って \(T_{n}\) を求める

最後に、値が分かっている項の関数として \(T_{n}\) を表す。ここでは \(k = \log n\) とすれば \(T_{n/2^{k}} = T_{1}\) となり、この値は定義より \(0\) に等しい:

\[ \begin{aligned} T_{n} &= 2^{k} T_{n/2^{k}} + kn - 2^{k} + 1 \\ &= 2^{\log n} T_{n/2^{\log n}} + n \log n - 2^{\log n} + 1 \\ &= n T_{1} + n \log n - n + 1 \\ &= n \log n - n + 1 \end{aligned} \]

これで再帰方程式が解けた！ \(n\) 要素のリストをマージソートするときに実行される比較の最大回数を表す閉形式の式が手に入った。解はかなり複雑な式なので、推測検証が失敗したのも不思議ではない。

検算として、求まった式が以前に計算した値を生成することを確認しておこう:

\[ \def\arraystretch{1.35}\begin{array}{c|c|c} n & T_{n} & n \log n - n + 1 \\ \hline 1 & 0 & 1 \log 1 - 1 + 1 = 0 \\ 2 & 1 & 2 \log 2 - 2 + 1 = 1 \\ 4 & 5 & 4 \log 4 - 4 + 1 = 5 \\ 8 & 17 & 8 \log 8 - 8 + 1 = 17 \\ 16 & 49 & 16 \log 16 - 16 + 1 = 49 \end{array} \]

さらなる検算として、数学的帰納法による明示的な証明を書くこともできる。証明で最も重要な帰納ステップは定義代入のステップ 2 で終わっているので、証明は簡単に書けるだろう。