配列を合体しながらソートする「マージソート」とは?

  • 2016/08/09 14:42:55
目次
  • 1:マージソートのアルゴリズム
  • 2:マージソートの利点と欠点

マージソートはバケットソートやバブルソートに比べて少し複雑なソートアルゴリズムです。

マージソートのアルゴリズム

マージソートの基礎になっているのは配列の合体(マージ)です。

予めソートされた2つの配列を合体させる時に、小さい値から先に並べて合体させれば、新しくできた配列もソートが完了しているという理屈が元になっています。

今回の例では以下の数値の配列をソートしたいものとします。

ms1

先ずマージソートでは配列を分割していきます。

この例では最後に要素2つの配列が4つできました。

ms2

この配列の中で値の大小をソートします。これは
以下のようになるかと思います。

ms3

今度はこれを統合していきます。まずは要素2つの配列を要素4つの配列になるように合体していきます。
合体には2つの配列の先頭を比べて小さい方を取り出して1つの配列となるよう並べていくことで行えます。

前の処理で配列はソートがされているので、配列の先頭がその配列の中で最小値になっているはずです。
そのため単純に配列の先頭を比較しながら並べていけばソートされていることになります。
ms4

さらに合体していきます。先ほどと同じようには2つの配列の先頭を比べて小さい方を取り出して1つの配列となるよう並べていくようにします。

最後の合体でソートが完了します。
ms5

マージソートの利点と欠点

マージソートはソートアルゴリズムの中でも計算効率が高いアルゴリズムです。また実装に依存してしまう部分もありますが、安定ソートにできます。

各配列の比較並び替えは個別の計算なので、並列処理とも親和性があると言えます。

しかし配列の要素が多いと、配列の分割と合体がかなりの数発生することもあり処理効率が落ちることになります。

マージソートはメモリ上の数値ソートよりも、ハードディスク上のファイルのソート等に向いていると言われます。