マージソート Merge Sort

マージソートは、高速でかつ安定なソートアルゴリズムです。しかも、効率はやや劣りますが、クイックソートと比べると実装が簡単で理解もし易いアルゴリズムです。高速で安定という特徴から、様々なところで実用されています。

マージソートのアルゴリズムは分割統治法を応用します。そして、マージソートは分割統治法を説明するための最も良い例ともなるので、分割統治法のアイデアもついでに知ることができます。下図は、マージソートの流れを表しています。

ステップ1	配列による入力データ
ステップ2	配列を２つに分割する
ステップ3	分割された部分配列をさらに分割する
ステップ4	分割された部分配列をさらに分割する
ステップ5	部分配列の要素数が 1 でこれ以上分割することができないので、2 つの部分配列を統治する。統治するときに要素を昇順にソートする
ステップ6	分割された部分配列をさらに分割する
ステップ7	2 つの部分配列を統治する。統治するときに要素を昇順にソートする
ステップ8	2 つの部分配列を統治する。統治するときに要素を昇順にソートする. ポイント：これら 2 つの部分配列の要素はすでにソート済みである
ステップ9-14	同様に、ステップ 2 で分割された部分配列を分割-統治する
ステップ15	2 つの部分配列を統治する。統治するときに要素を昇順にソートする. ポイント：これら 2 つの部分配列の要素はすでにソート済みである. 配列のソートが完了する

マージソートの流れの論理的な構造は、ツリー（木）となっていますが、実装するためにツリーのデータ構造を用いる必要はありません。しかし、データを配列で処理する場合、マージソートはその倍のメモリ空間を必要とすることが、マージソートの欠点でもあります。実装は以下のように非常にシンプルな構成となります。

void main(){
    mergeSort( 配列全体 );
}

void mergeSort( 部分配列 ){
    if ( 部分配列の要素数が１以下 ) return;
    mergeSort( 部分配列の前半 );
    mergeSort( 部分配列の後半 );
    merge( 部分配列 );
}

void merge( 部分配列 ){
    すでにソートされている部分配列の前半と後半を昇順に統治（マージ）する.    
}

マージソートのプログラムは、mergeSort と merge の２つの部分から構成されています。まず、配列全体を指定した mergeSort を呼び出します。mergeSort は与えられた配列を前半後半の２つに分割します。その２つについてそれぞれさらに mergeSort を行います（再帰により実現する）。mergeSort は配列の要素数が 1 以下のときは何もせずに終了します。そして、各 mergeSort の最後で、分割された前後２つの配列を merge します。merge を実行する時点で、mergeSort( 部分配列の前半 ) と mergeSort( 部分配列の後半 ) がすでに終了しているので、merge はすでにソートされている部分配列の前半と後半に対して実行されます。言い換えれば、merge の役割は、すでにソートされている２つの部分配列を１つのソートされた部分配列にすることです。

プログラム例：部分配列の先頭のインデックスを left、部分配列の(末尾 + 1)のインデックスを right とした場合

void mergeSort( Data data[], int left, int right ){
    if ( left >= right - 1 ) return;
    int mid = ( left + right ) / 2;
    mergeSort( data, left, mid );
    mergeSort( data, mid, right );
    merge(data, left, mid, right );
}

void merge( Data data[], int left, int mid, int right ){
    Data L[MAX/2 + 2], R[MAX/2 + 2]; // temporal buffers
    int n1 = mid - left; // size of L
    int n2 = right - mid; // size of R
    for ( int i = 0; i < n1; i++ ) L[i] = data[left + i];
    for ( int i = 0; i < n2; i++ ) R[i] = data[mid + i];
    L[n1].key = R[n2].key = INT_MAX;
    int i, j;
    i = j = 0;
    for ( int k = left; k < right; k++ ){
        if ( L[i] <= R[j] ) { data[k] = L[i++]; }
        else data[k] = R[j++];
    }
}

この merge 関数は番兵を使ってやや巧妙な処理をしています。以下の図は、この merge のメカニズムをカードの操作で表したものです。左右にカードの束があり、各束のカードは小さい順に整列されているものとします。そして、カードの最下部に番兵としてジョーカーを追加配置します。

マージの処理は、各カードの山のてっぺんの値を比べ、小さい方を選択して順番に並べていきます。この操作の過程で、あるカードとジョーカーを比べる局面が発生しますが、ジョーカーが選ばれることはありません。つまり、番兵にはどのカード（数字）と比べても負けることのない大きな数を割り当てるのです。

ジョーカーすなわち番兵の設置によって、マージの際にカードの束が空になったか否かのチェックをする必要がなくなります。なぜなら、カードを選択する回数を、ジョーカーを除いたカードの合計値とすれば、ジョーカーが比べられることも、カードの束が空になることもないからです。束が空になったか否かのチェックは、プログラム上では配列の範囲を超えるか否かのチェックとなるので、番兵の設置は処理の高速化にも繋がり（微々たるものですが、）プログラムが読みやすくなります。




次に示す、merge のプログラムは、さらに巧妙なテクニックを用いています。プログラムの動作を考えてみましょう。

void merge( Data data[], int left, int mid, int right ){
    Data T[MAX]; // temporal buffer
    int i, j;
    for ( i = left; i < mid; i++ ) T[i] = data[i];
    for ( i = mid, j = right - 1; i < right; i++, j-- ) T[i] = data[j];
    i = left; j = right - 1;
    for ( int k = left; k < right; k++ ){
        if ( T[i] <= T[j] ) { data[k] = T[i++]; }
        else { data[k] = T[j--]; }
    }
}

マージソートの計算効率は、データがどのような特徴を持っていても O(nlogn) となります。上図に示したマージソートの論理的構造であるツリーの深さは、データの数を n とすれば logn となり、各階層で n 回の比較演算がなされるからです。

実戦でマージソートを自分で最初から実装することはまずないと思われますが、分割統治法、再起、番兵のアイデア、などを学べる良いアルゴリズムの１つではないでしょうか。