マージソート

マージソート (mergesort) はプログラム内蔵式の汎用コンピューター用に作られた最も古いアルゴリズムの一つです。このアルゴリズムは John von Neumann (ジョン・フォン・ノイマン) によって 1945 年に開発され、 1947 年に Herman Goldstine (ハーマン・ゴールドスタイン) との共著で発表されました。このプログラムは EDVAC 用に作られた計算用途ではないプログラムのうち最初期のものでもあります1。マージソートは次のステップからなります:

  1. 入力の配列をほぼ同じ長さの二つの小配列に分割する。
  2. 二つの小配列に再帰的にマージソートを行う。
  3. ソートされた二つの小配列をひとつの配列に組み合わせる (マージする)。
\[ \begin{array}{rc} \text{入力} :& \texttt{S O R T I N G E X A M P L} \\ \text{分割} :& \texttt{S O R T I N | G E X A M P L} \\ \text{左の再帰} :& \texttt{I N O R S T | G E X A M P L} \\ \text{右の再帰} :& \texttt{I N O R S T | A E G L M P X} \\ \text{マージ} :& \texttt{A E G I L M N O P R S T X} \end{array} \]
図 1.5. マージソートの例

最初のステップは配列の長さを \(2\) で割るだけで済むので簡単です。二つ目のステップは再帰の妖精に任せることができます。そのため本当の作業と呼べるのは最後のマージのステップだけです。

完全なマージソートのアルゴリズムを次に示します。再帰的な構造を明らかにするために、マージのステップをサブルーチンとして別にしています。\(\textsc{Merge}\) も再帰的なことに注意してください。最初に出力の先頭の要素を見つけ、それから残りの入力を再帰的にマージしています。

procedure \(\texttt{MergeSort}\)(\( A[1..n] \))

if \( n > 1 \) then

\( m \leftarrow \lfloor n/2 \rfloor \)

\(\texttt{MergeSort}\)(\( A[1..m] \)) \(\quad \hphantom{{},+1}\) ⟨⟨再帰!⟩⟩

\(\texttt{MergeSort}\)(\( A[m+1..n] \)) \(\quad\) ⟨⟨再帰!⟩⟩

\(\texttt{Merge}\)(\( A[1..n], m \))

procedure \(\texttt{Merge}\)(\(A[1..n], m\))

\( i \leftarrow 1;\ j \leftarrow m+1 \)

for \( k \leftarrow 1 \) to \( n \) do

if \( j > n \) then

\( B[k] \leftarrow A[i];\ i \leftarrow i + 1 \)

else if \( i > m \) then

\( B[k] \leftarrow A[j];\ j \leftarrow j + 1 \)

else if \( A[i] < A[j] \) then

\( B[k] \leftarrow A[i];\ i \leftarrow i + 1 \)

else

\( B[k] \leftarrow A[j];\ j \leftarrow j + 1 \)

for \( k \leftarrow 1 \) to \( n \) do

\( A[k] \leftarrow B[k] \)

図 1.6. マージソート

正しさ

このアルゴリズムが正しいことを示すには、長い付き合いである帰納法を二回適用します。最初は \(\textsc{Merge}\) サブルーチンに適用してから、次にトップレベルの \(\textsc{MergeSort}\) アルゴリズムに適用します。

命題 1.1 小配列 \(A[1..m]\) と \(A[m+1..n]\) が正しくソートされているならば、\(\textsc{Merge}\) は二つの小配列を正しくマージする。

証明 \(A[1..n]\) を任意の配列、 \(m\) を小配列 \(A[1..m]\) と \(A[m+1..n]\) がソートされているような任意の整数とする。0 から \(n\) までの任意の \(k\) について、\(\textsc{Merge}\) の残り \(n - k - 1\) 回のメインループが \(A[i..m]\) と \(A[j..n]\) を \(B[k..n]\) に正しくマージすることをこれから示す。証明はこれからマージする要素の数 \(n - k + 1\) に関する帰納法で行う。

\(k > n\) ならば二つの小配列は空なので、何もしないことでマージが完了する (これが帰納法の証明のベースケースである)。そうでない場合、メインループの \(k\) 回目の反復には 4 つの場合がある。

  • \(j > n\) なら小配列 \(A[j..n]\) は空なので \(\min \left(A[i..m] \cup A[j..n] \right) = \) \(A[i]\)
  • \(i > m\) なら小配列 \(A[i..m]\) は空なので \(\min \left(A[i..m] \cup A[j..n] \right) = \) \(A[j]\)
  • それ以外の場合で \(A[i] < A[j]\) ならば \(\min \left( A[i..m] \cup A[j..n] \right) = A[i]\)
  • それ以外の場合 \(A[i] \geq A[j]\) だから \(\min \left( A[i..m] \cup A[j..n] \right) = A[j]\)

四つの場合全てにおいて、\(B[k]\) には \( A[i..m] \cup A[j..n] \) の最小の要素が代入される。\(B[k] \leftarrow A[i]\) という代入が起こる二つの場合では、再帰の妖精、おっと、帰納法の仮定より残りの \(n - k\) 回のメインループで \(A[i+1..m]\) と \(A[j..n]\) が \(B[k+1..n]\) にマージされる。同様に残りの二つの場合でも帰納法の仮定より小配列は正しくマージされる。 \(\Box\)

定理 1.2 \(\textsc{MergeSort}\) は入力の配列 \(A[1..n]\) を正しくソートする。

証明 \(n\) に関する帰納法で示す。\(n \leq 1\) のときアルゴリズムは何もしないが、これは正しい動作である。そうでなければ帰納法の仮定より二つの小配列は正しくソートされる。命題 1.1 より、その小配列を \(\textsc{Merge}\) 関数に入力したときの出力はソートされた全体の配列だから、\(\textsc{MergeSort}\) は確かに元の配列をソートする。 \(\Box\)

解析

\(\textsc{MergeSort}\) アルゴリズムは再帰的なので、その実行時間は再帰方程式で表されます。 \(\textsc{Merge}\) は決まった処理を要素ごとに行う for ループなので、実行時間は \(O(n)\) です。よって \(\textsc{MergeSort}\) の実行時間 \(T(n)\) について次の再帰方程式を得ます: \[ T(n) = T(\lceil n/2 \rceil) + T (\lfloor n/2 \rfloor) + O(n) \]

分割統治法を使ったときに生じるほとんどの再帰方程式と同様に、この式に出てくる床関数と天井関数は無視できます (この章の最後で説明される定義域変換というテクニックを使います)。よって \(T(n) =\) \(2T(n/2) + O(n)\) です。 “全ての段階で等しい” 場合の再帰木の方法 (同じくこの章で説明されます) を使うと \(\pmb{T(n) = O(n \log n)}\) という閉じた答えがすぐに分かります。再帰木について (まだ) 知らなかったとしても、 \(T(n) = O(n \log n)\) という答えは帰納法で確認できます。


  1. Goldstine と von Neumann が提案したのは再帰的でないマージソートであり、現在ではボトムアップマージソートと呼ばれます。当時、大きなデータセットのソートには二進基数ソートの一種を使ってパンチカードを生成する専用用途の機械 ――ほとんどが IBM 製―― が使われていました。EDVAC は IBM の専用用途のソーターよりも速く、さらに “人の仲介や追加の設備を必要とすることなく” ソートができることから、Von Neumann は EDVAC が「汎用 (all purpose)」機械であり、専用用途の機械はもう必要なくなったという (正しい!) 主張をしました。[return]