[アルゴリズム] マージソートのプログラミング（解説）

ソートアルゴリズムプログラミングの第5弾目になりますが、これもかなりメジャーなソートアルゴリズムである「マージソート」をコーディングしてみたいと思います。 簡単に言うと、ソートする数値配列を一度細かく分割していき、後半はそれらを大小比較しながらマージしていくやり方です。 すると最後に、全ての値でソートされているという結果になるんですね。

手順解説

1.(分解)数値郡（配列）を2分割ずつしていく

数値郡が端数の場合は、どちらかに含める

2.(分割)分割結果の配列が2つ以下になるまで繰り返す

3.（比較）数値をそれぞれ比較する（数の低い順にする）

４.（結合）比較した同士をくっつける

5.（結合）全ての分割された数字郡がひとつになるまで繰り返しつなげる

※この時、くっつけた状態での大小比較を行う

完了

図解

手順を図で書くと以下のようになります。

検討

このアルゴリズムで最初不思議に思ったのが、マージしていく課程でその中の値を全て処理しているので、いっその事、最初に２分割した状態でくっつける際にソートするだけではダメなのかと考えていたところ、 １対１にまで細分化する意味は、複数対複数という状態で左から小さい順になっているグループにしておくことで、比較処理を楽にしている事に気がついた。 確かに、バブルソートは考え方は楽だが、このマージソートの方が、高速に処理できるように思われる。

リンク

Wikipedia - https://ja.wikipedia.org/wiki/マージソート たくさんのプログラム言語でアルゴリズム学習

• 解説
• Javascript
• PHP
• Python
• Shell
• AWK
• C言語
• Go言語
• Ruby