MENU
なお
じゃぱざむ運営主
20歳 | WEBメディアの会社で部長をやりながら、じゃぱざむ・特化メディア・WEB制作~コンサル・SEOディレクター・投資・就活相談など幅広くやっています。
いまい
エンジニア志望の大学生
21歳 | 理系の大学3年生|Webアプリ開発を勉強中。クラウド系の自社開発企業に内定。じゃぱざむでは、IT系記事の執筆とアイキャッチ画像の作成をしています。
【完全ガイド】大学生でもプログラミングで稼ぎ始めるためのロードマップ

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

記事上バナー
テックキャンプの記事上バナー
レイズテックの記事上バナー
テックブーストの記事上バナー
  • マージソートの基本的な考え方
  • マージソートのわかりやすい解説動画
いまいのアイコン画像いまい
こんにちは!
今井(@ima_maru)です。

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

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

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

タップして好きなところから読めます

マージソート(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を少ない処理数で作ることができるでしょうか?

いまいのアイコン画像いまい
ここで、闇雲にソートの処理を書いていては、バブルソートや挿入ソートといった遅いソートと何も変わりません。

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

ソート済み配列の基本的な性質
  • 配列Xの中で、一番小さい値は配列Xの先頭の値「1」。
  • 配列Yの中で、一番小さい値は配列Yの先頭の値「2」。

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

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

いまいのアイコン画像いまい
何が言いたいかというと、配列の2番目以降の値は、その配列の1番目の値以上だから候補から外れるよねってことです。つまり比較対象は先頭の値のみでよいのです。

これからわかることは、配列の先頭を比べながら小さい値のほうを配列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に入れてマージ完了です。

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

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

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

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

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

  • 降順(大きい値から小さい値)になるようにソート
  • 徐々にサイズが大きくなっていくことがイメージしやすい
  • 分割から併合(マージ)の流れがわかりやすい。

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

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

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

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

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

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

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

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

いまいのアイコン画像いまい
最後までご覧いただきありがとうございます。

この記事が気に入ったら
フォローしてね!

よかったらシェアしてね!
タップして好きなところから読めます
閉じる