マージソートとは？図を使ってわかりやすく解説します！

今回は、ソーティングルゴリズムの一つ「マージソート」について、触れていきます。

できるだけわかりやすく解説していきたいと思います！

それでは解説に移ります！

マージソート（Merge sort）とは？

マージソートとは、「ソートアルゴリズム」の一種で、とても速いといわれている中の一つです。

非常に安定しているソートで、考え方もわかりやすいです。

ここではマージソートの主な考え方について書きます。

マージソートの基本的な処理は、分割とマージに分かれます。

最小単位まで分割してから考える「分割統治法」

マージソートは、クイックソートと同じく「分割統治法」という手法を使ったソートアルゴリズムです。

分割統治法とは、問題を細かく分け、それらすべての問題を解くことで、全体の問題を解いていくという手法です。

マージソートでは初めに、配列のデータ数が1個になるまで分割するという手法を取ります。

当たり前ですが、配列のデータ数が1個なら、ソート済みの配列とみなすことができますよね。

例えば、「1」もデータ数1の配列です（ソート済み）。

そうしたら次に、二つのソート済み配列を合体させて一つのソート済み配列をつくるということをします。

実はこれが「マージ」と呼ばれる処理なのですが、ここでは説明をすっ飛ばします。

例えば、「1」と「5」から「1,5」という配列を作ります。

これで新しい配列のデータ数は2個となりました。

次に、「1,5」と「2,8」から「1,2,5,8」という配列を作れば、これでデータ数は4個となります。

次は、「1,2,5,8」と「3,4,6,7」から「1,2,3,4,5,6,7,8」という配列を作れば、これでデータ数は8個となります。

こんな風に、まずはデータ数を1から始める。

そして、「マージ」という処理によって二つのソート済み配列を合体し、一つのソート済み配列を生成する。

マージを繰り返すことでソート済み配列のデータ数を増やしていく。

最終的に、元のデータと同じ大きさのソート済み配列が完成するというのがマージソートの流れになります。

動画で見るととてもわかりやすいです。

はじめは凸凹だった棒グラフが、徐々にサイズの大きな昇順のグループになっていく様子が見てわかります。

最後は大きな二つのグループがマージされてソートが完了していますね。

マージソートの速度の秘密は「マージ」にある

マージソートの速さのカギとなるのは、ソート名にも入っている「マージ」という処理です。

「マージ」とは、二つのソート済みの配列を合体し、一つのソート済みの配列を生成する処理のことを言います。

イメージは以下のような『スライム』の合体を想像してみてください。

こんなイメージです。

実際のデータとして表せば、以下のように

昇順ソート済みの「配列1」と
昇順ソート済みの「配列2」を合体して、

昇順ソート済みの「配列3」を生成する処理です。

マージソートが速い理由は、この「マージ」という処理にひと工夫を加えているからです。

その工夫は、それぞれの配列がすでに「ソート済み」ということを利用する点にあります。

例えば、以下のような昇順ソート済みの配列Xと配列Yがあったとして、それらをマージした配列Zを作ることを考えます。

どのようにすれば、配列Zを少ない処理数で作ることができるでしょうか？

マージソートでは、以下の性質を使います。

つまり、配列Zの一番初めの場所に入る値は、「1」か「2」の二択ということになります。

なぜかというと、配列Zの一番初めに入るのは、配列Xと配列Y全体の一番小さい値であるからです。

これからわかることは、配列の先頭を比べながら小さい値のほうを配列Zに入れていけば良いということになります。

実際にマージの流れを見てみましょう。

この場合、「1<2」なので、配列Xの「1」が配列Zの1番目に入ります。

次は、「3>2」なので、配列Yの「2」が配列Zの2番目に入ります。

次は、「3<5」なので、配列Xの「3」が配列Zの3番目に入ります。

次は、「4<5」なので、配列Xの「4」が配列Zの4番目に入ります。

次は、「7>5」なので、配列Yの「5」が配列Zの4番目に入ります。

このように比較を行っていけば、今回の例だと、最終的に配列Xの値がなくなり、配列Yの値のみが残ります。（以下のように）

こうなれば、配列Yの値をそのまま配列Zの最後の部分に入れて終わりです。（今回は残った値が1つだけでしたが、複数残った場合も同様です。）

なので、残った8を配列Zに入れてマージ完了です。

このように、それぞれの配列がすでにソートされているということを利用して、残っている配列の要素の先頭を比較していくということを行っています。

この工夫により、マージソートは無駄な比較が省けてとても効率の良いソート方法となっています。

マージソートのアルゴリズム、どのように実現するか？

わかりやすい動画を張っておきますので参考にしてみてください。

マージソートのわかりやすい解説動画

マージソート以外の高速なソーティングアルゴリズム！

最後に、ほかの高速なソーティングアルゴリズム、また、基本的なソーティングアルゴリズムの動画をご紹介して終わりにしたいと思います。

ソーティングアルゴリズムの比較動画

これはいろいろなソーティングアルゴリズムを紹介している動画です。

左上にソート名が書いてあります。

また、ソートするデータ数や速度設定が違うので注意してください。

クイックソートについては以前に書いた記事があるので、興味がある方は是非ご覧ください。

以上「マージソートとは？図を使ってわかりやすく解説します！」でした！