前回は挿入ソートを実装した。

今回はマージソートを実装していこう。このマージソート、挿入ソートと比べると格段に高速なアルゴリズムである。

マージソートという言葉、何かの呪文みたいですよね。

マージソート

アルゴリズム

手っ取り早く、ASCII.jpデジタル用語辞典を引用するとマージとは次の意味である²。

複数のデータを、決まった手順や規則に従って1つにまとめること。併合とも呼ぶ。データベースでは、複数のテーブルのレコードを比較し、項目が一致するデータを取り出して新しいテーブルとして表示することをいう。

マージソートは複数あるデータを1つにまとめるソート方法ということである。ただしこのアルゴリズムに入力として与えられるデータ列は挿入ソートと同じで1つのみだ。マージソートでは、この1つのデータ列を分割して、さらに分割して……と繰り返していく。分割を繰り返していくと分割されたデータ列の要素はついには1つのみとなる。分割したあとには次の要領でマージを行っていく。

1つの要素を持ったデータ列が $n$ 個ある。これらのデータ列の2つずつをマージするのだが、要素が数字順となるようにマージする。すると、2つの要素を持つ、ソートされたデータ列が $n/2$ 個得られる。さらにデータ列の2つずつを同様にマージする。 4つの要素を持つ、ソートされたデータ列が $n/4$ 個得られる。

以上を繰り返していくと、要素数 $n$ のソートされたデータ列が得られるのである。

実例

トランプのカードが8枚配られたとしよう。めくってみるとの番号は次のとおりであったとする。

4, 3, 7, 5, 8,1, 2, 6

分割

まず半分に分ける。

4, 3, 7, 5
8, 1, 2, 6

さらに半分に分ける。

4, 3
7, 5
8, 1
2, 6

もういっちょ。

これで、初めは1つの山札 (8枚) であったのが、8つの山札 (各1枚) に分割された。上記の分割の流れがわかりやすいように表にすると、次の通り。

-	山札の数	各山札の枚数	山札のカードの番号
初期時	1	8	4, 3, 7, 5, 8, 1, 2, 6
分割 1	2	4	4, 3, 7, 5				8,1, 2, 6
分割 2	4	2	4, 3		7, 5		8, 1		2, 6
分割 3	8	1	4	3	7	5	8	1	2	6

マージ

さらにマージすることによりソートを行う。分割した回数だけ、つまり3回マージを行えばソートが完了する。次のようにマージされていく。各マージ時に、ソートされた山札が出来上がっていく過程がわかるかと思う。

-	山札の数	各山札の枚数	山札のカードの番号
初期時	1	8	4, 3, 7, 5, 8, 1, 2, 6
分割 1	2	4	4, 3, 7, 5				8,1, 2, 6
分割 2	4	2	4, 3		7, 5		8, 1		2, 6
分割 3	8	1	4	3	7	5	8	1	2	6
マージ 1	4	2	3, 4		5, 7		1, 8		2, 6
マージ 2	2	4	3, 4, 5, 7				1, 2, 6, 8
マージ 3	1	8	1, 2, 3, 4, 5, 6, 7, 8

マージ時のソート方法

マージ時のソート方法について、3回目のマージ (上記表の "マージ 3") を例に説明する。 (1、2回目のマージについても要領は同じである。)

さて、目の前に次の2つの山札がある。各山札はソートが済んでいる、と仮定する。

3, 4, 5, 7
1, 2, 6, 8

まず、各山札の1枚目の数字を比較し、小さい数字のカードを山札から除外する。 "3" と "1" なので "1" のほうが小さい。なので、山札のカードは次のとおりとなる。

3, 4, 5, 7
2, 6, 8

除外したカード (数字 1) は新しい山札とする。そしてまた上記の要領でカードを除外し、新しい山札に加える。これで新しい山札は 1, 2 となる。さらに繰り返していくと、結局ソートされた山札が得られる。

マージを行うにあたって、各山札はソート済みであると仮定した。ソート済みの山札をマージするのであれば、新しい山札もソート済みということが保証されることはわかるかと思う。では、1回目のマージのときに各山札がソート済みであれば、最終的に得られる山札もソート済みということが保証されるということになる。

面白いことに、マージ 1 のときには各山札のカードは1枚なので既にソート済みなのである。

実装

マージソートを行う関数 merge_sort とマージを行う関数 merge を実装する。関数 merge_sort の中では関数merge および再帰的に関数 merge_sort を呼び出す。

基本線はアルゴリズムイントロダクションの擬似コードと同様に実装したが、部分配列の作成部分等は適宜変更している。

まず merge は次の通りの実装となっている。

def merge(A, p, q, r):
    """配列 A の部分配列 (2つ) をマージして配列 A に格納する。
    部分配列はインデックス p, q, r で指定する。

    Args :
        A (list of numbers): 数値のリスト
        p (int) : 1つ目の部分配列の開始インデックス
        q (int) : 1つ目の部分配列の終了インデックス
        r (int) : 2つ目の部分配列の終了インデックス
    """

    L = A[p: q + 1]
    R = A[q + 1: r + 1]

    inf = float('inf')
    L.append(inf)
    R.append(inf)

    i = j = 0
    for k in range(p, r + 1):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

部分配列を2つ作成し、それらの部分配列の先頭の数値を比較しソートを行う。番兵を使ってアルゴリズムを単純にしている点に注意。

12-13 行 : 部分配列の作成
- マージを行う部分配列を作成する。
15-17 行 : 番兵の追加
- 部分配列の末尾に番兵 (無限大の数値) を追加する。
- これにより部分配列の先頭値の比較時に、配列が空でないかの確認が不要となる。
19- 26行 : マージ
- 部分配列の先頭値の比較を行い、小さい方を配列に追加する。
- 実際には A[k] の値を更新する。
- これにより A[p..k] の値はソート済みということになる。
- インデックスを表す変数 i、j、k の意味は次のとおりである。
  - i は1つ目の部分配列の先頭のインデックスである。
  - j は2つ目の部分配列の先頭のインデックスである。
  - k はマージした配列の末尾のインデックスである。

関数 merge_sort は次の通り実装した。

def merge_sort(A, p, r):
    """マージソートを行う。

    Args :
        A (list of numbers) : 数値のリスト
        p (int) : マージを行う部分配列の開始インデックス
        r (int) : マージを行う部分配列の終了インデックス
    """

    if p < r:
        q = int((p + r) / 2)
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)

10-14 行
- マージソートを行う。
  - 11-13 行 : 配列を半分に分割し、それぞれの部分配列に対してマージソートを実行する。
  - 14 行 : 上記によりソートされた各部分配列をマージする。
- p < r を満たさないとき (部分配列が空のとき) には何もしない。

次のようにマージソートを実行したところ、しっかりとソートされている。

import numpy as np

numbers = np.random.randint(255, size=10).tolist()
print('ソート前:', numbers)
p = 0
r = len(numbers) - 1
merge_sort(numbers, p, r)
print('ソート後:', numbers)

ソート前: [50, 127, 149, 28, 164, 196, 253, 46, 13, 175]
ソート後: [13, 28, 46, 50, 127, 149, 164, 175, 196, 253]

関数 merge_sort はソートを行う範囲を引数として与える必要がある。開始と終了のインデックスはもちろん 0 と (配列の長さ - 1) である。

アルゴリズムという本筋からずれるが、ユーザーがこの関数を呼び出すときには自動で配列の範囲を判別してほしいと考えるだろう。そこで次のようにオプション引数を使って p と r の指定を省略することができる。

def better_merge_sort(A, p=None, r=None):
    """マージソートを行う。

    Args :
        A (list of numbers) : 数値のリスト
        p (int) : マージを行う部分配列の開始インデックス
        r (int) : マージを行う部分配列の終了インデックス
    """

    if p is None:
        p = 0
    if r is None:
        r = len(A) - 1

    if p < r:
        q = int((p + r) / 2)
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)

次のように配列の範囲を指定せずに実行できる。

numbers = np.random.randint(255, size=10).tolist()
print('ソート前:', numbers)
better_merge_sort(numbers)
print('ソート後:', numbers)

ソート前: [233, 18, 114, 230, 20, 32, 32, 6, 20, 54]
ソート後: [6, 18, 20, 20, 32, 32, 54, 114, 230, 233]

マージソートの計算量

関数 merge_sort ではまず配列の分割を行うが、これはただ配列の半分となるインデックスを求めるだけで定数時間の処理となるため、ここでは無視してしまおう。問題は再帰的に呼び出す関数 merge である。どのように計算量を算出すればよいか。

初めにトランプのカード $n=8$ 枚を使った実例と同様に表にまとめてみると次のようになる。初めは8枚の山札に対して関数を実行する。次は4枚の山札に対しての関数の実行を2回、その次は2枚に対して4回、1枚に対して8回、となる。

関数 merge_sort は適用する山札の数に比例する計算量となる。再帰が深くなるたびに半分の計算量となるが、再帰の回数が2倍となる。するとうまい具合に、各再帰の深さでの計算量の合計が同じ量となる。再帰の最深は $\log_2 n + 1$ となるから、結局計算量は $cn\log_2 n + cn$ となる。

※本書によるとこのような計算量ということになるかと思うのだが、確信が持てていない。
　再帰の深さ 4 では merge_sort は p = r となって処理を行わない、つまり条件判定による定数時間のみの計算量となり、計算量は $cn\log_2 n$ となるような気がする。
　計算量の増加についての結論については変わらないので気にしないことにした。

再帰の深さ	山札の数	各山札の枚数	計算量								計
1	1	8	$cn$								$cn$
2	2	4	$cn$ /2				$cn$ /2				$cn$
3	4	2	$cn$ /4		$cn$ /4		$cn$ /4		$cn$ /4		$cn$
4	8	1	$cn$ /8	$cn$ /8	$cn$ /8	$cn$ /8	$cn$ /8	$cn$ /8	$cn$ /8	$cn$ /8	$cn$
総計算量											$cn\log_2 n + cn$

計算量について、 $\theta$ 記法というものを導入し、もっと抽象的にしよう。例えば、計算量が $c_1n^{2} + c_2n + c_3$ に比例するアルゴリズムがあるとする。興味がある項は、 $n$ による増加量が最も大きい $c_1n^{2}$ である。さらに $c_1$ にもあまり興味がない。そこで、このアルゴリズムの計算量を $\theta(n^{2})$ と表記する。