1次、2次元配列のマージソート方法

マージソート

クイックソートよりかなり優れたソート方法です。元のデータの並び方が悪いと、クイックソートの効率はバブルソート並みに悪化します。マージソートはそのようなことが無いので効率よくソートを行うことのできるアルゴリズムです。

大まかな名がとしては以下の手順となります。

1. 全体を2分割
2. それぞれをさらに2分割
3. 全てのブロックが1になるまで繰り返す
4. 分割完了したら、隣同士のブロックを整列しながら併合
5. さらに隣同士をマージ
6. 全体が1つになるまで繰り返す

配列のソートアルゴリズムに関しては、いろいろな場所で紹介されている。ただし1次元配列の場合がほとんどで、2次元配列の場合のサンプルコードは見つけられなかった。

そこで1次および2次元配列のマージソートソフトを作成したので、ここに残しておく。

1次元配列のマージソート

2次元配列のマージソート

注意： 元となる２次元配列ar(x, y)のyの要素数はソートするデータ要素数に+1しておくこと

ソースコード