高速なソートアルゴリズム「マージソート」を解説！

前回は、一つ目の高速なソートアルゴリズムであるクイックソートを解説した。

これはかなり高速なので、それで十分…ともいかない。

データ構造によっては、別のソートの方がよかったりもする。

今回は、二つ目のマージソートについて解説しよう。

前回のクイックソートと似ているため、混同しないよう注意してほしい。

シノ

前回と同じく、処理中の
データの動きに注目しよう！

前提知識

前回と同じく、以下の知識が必要となる。

• 再帰
• 分割統治法

これについては、別記事で解説しているので、そちらを参照してほしい。

【再帰・分割統治法】高速なソートアルゴリズム前提知識 -考え方編- | Shino’s Mind Archive

マージソート

では、早速マージソートのアルゴリズムを説明しよう。

まず、入力となるデータを、真っ二つに分解してしまう。

そして、それぞれでソートを行う。

これも、分割統治法に則って、同じ方法だ。

なお、分割はそれ以上できなくなるまで行う。

次にくっつけるのだが、この時がポイント。

それぞれの最初の要素を比較する。

そのうち、小さい方から順番に元の配列へ戻していく、という操作を行う。

これを繰り返すことで、最終的にソートが完了する、という考え方だ。

この、二つのソート済み配列をくっつける操作のことをマージと呼ぶ。

だから、マージするソート、マージソートというわけだ。

では、具体例を見ていこう。

ソートするのは、以下の配列だ。

では、分解していこう。

まず、真っ二つに。

このうち、左側に注目して進めよう。

再度、分割を行う。

この左側について、また分割をしてみよう。

さて、これ以上分割できない段階まで来た。

そうしたら、これらをくっつけていこう。

二つの列を見て、小さい方から順番に元に戻していく。

こうなる。

もう一つのdata[2]、data[3]も同じようにマージを行う。

次に、もう一段階上で同じようにマージしていこう。

今、二つの分割された配列は以下のようになっている。

これについて、先頭を順番に比較して、小さいものから順番に取っていこう。

順番に見ていくと…

• 2と1を比較し、1の方が小さい
• 2と4を比較し、2の方が小さい
• 7と4を比較し、4の方が小さい

この段階で、右側の領域には何も残らなくなったので、左に残っている7を持ってきてあげる。

そうすることで、以下のような並びが出来上がる。

これで、全体の左半分が完了だ。

残り、右半分でも同じことをしてあげると、この段階で以下二つの領域が出来上がっている。

ここまで来たら、最後のマージをしてあげよう。

先頭を比較しながら、小さいものを順番に取ってきてあげると…

このように、ソートが完成する。

大まかな流れはこのような感じだ。

クイックソートでは、分けるときに並び替えていた。

マージソートは、くっつける時に並び替える。

この違いに注意しておこう。

マージソートの計算量

これも高速なソートアルゴリズムの一つに分類されている。

ということは、ある程度速いソート、ということだ。

実際、計算量は\(O(n \log(n))\)でかなり高速だ。

とはいえ、見た目には見えない定数部分が大きいため、クイックソートには敵わない。

その他、実はマージソートは配列のソートには向かない。

なぜかというと、同じ領域だけの別の配列が必要になってしまうからだ。

実は、連結リストと呼ばれるデータ構造にすれば、この弱点を回避できる。

この連結リストも以前解説をしているので、そちらをご参照頂きたい。

【連結リスト・ヒープ】高速なソートアルゴリズム前提知識 -データ構造編- | Shino’s Mind Archive

マージソートのサンプルプログラム

最後に、サンプルプログラムをご紹介して終わりにしよう。

今回は、配列のソートを例にしている。

連結リスト版は、是非自分で組んでみて欲しい。

function MergeSort(data, low, high){
    if(low >= high){
        return;
    }
    let mid = Math.floor((low + high) / 2);

    MergeSort(data, low, mid);
    MergeSort(data, mid + 1, high);

    let tmp = [];

    for(let i = low; i <= mid; i++){
        tmp[i] = data[i];
    }
    for(let i = mid + 1, j = high; i <= high; i++, j--){
        tmp[i] = data[j];
    }

    let i = low;
    let j = high;
    for(let k = low; k <= high; k++){
        if(tmp[i] <= tmp[j]){
            data[k] = tmp[i];
            i++;
        }else{
            data[k] = tmp[j];
            j--;
        }
    }
}

ちょっと、後半の動きについて補足しておこう。

今回、一つの作業用配列だけを使って実装している。

このとき、どのように考えているかだ。

まず片方の領域は、普通に配列に格納している。

そして、もう一つは逆向きにして、後ろから順番に入れている。

そして、両側から比較して、小さいものを元の配列に戻す、ということをしている。

jが逆向きなのは、そういう意図だ。

このあたり、気を付けて見ていってほしい。

おわりに

今回は、マージソートについて解説を行った。

何度も書いているが、クイックソートと混同しないよう気を付けよう。

残る高速なソートアルゴリズムはヒープソートのみ。

これも、次回解説することにしよう。

ただ、ヒープソートはこれまでとは考え方ががらっと変わる。

その点をご注意いただきたい。