書くこと思いつかないからマージソートについてまとめる

前回の記事で1週間に2記事書くと宣言した手前、何も書くことが思いつかないので自分の勉強のためにもマージソートについてまとめる。

マージソートのざっくりイメージ

「マージ(merge)」という単語の意味する通り、一度配列をバラバラに分解してから、結合していきながらソートを遂行するアルゴリズム。

下はイメージ図。ガバガバだけどないよりは良いだろう

バブルソートなどのO(N²)のアルゴリズムよりも早い。（後述）

マージソートの美しいところはマージの仕方にある。

マージソートはマージする部分配列がそれぞれソート済みであるということをうまく使って、効率的にソートを完了する。

具体的に見ていく。

下の図はマージソートが実行されている様子をあらわしたもの(まぁ1ステップ分しか書いてないのだが。)

マージソートではマージ時に部分配列の未マージ状態の端の要素のみを比較する。(下図においては1と5)

これは部分配列がソート済みであるために他の要素はマージ対象になりえないためである。(下図においてはマージ先の配列の0番目の要素(最小値)を探す際、最小値になり得るのは部分配列の最小値のどちらか(1と５)しかなりえない)

この操作を繰り返すことでソートをされたマージ配列ができる。

さらに、このマージ操作は2つの部分配列長分の繰り返し操作しか行わないので、計算量はO(N+M)となる(各部分配列長をN, Mとして)

マージソートは各段階のマージにO(N)、マージをlog2N段階分おこなうので、計算量はO(NlogN)となる。

バブルソートなどよりも時間計算量は優れていると言える。

しかし、マージソートはマージのためにN分のメモリ領域が入力の別に必要になるというデメリットがある。(wikiによるとそれがいらないようにインプレースで処理を行うマージソートのバリエーションもあるらしい。)