マージソートをトレースしてみる

マージソートとは、

大量のデータをいくつかのグループに分割し、整列と併合を行う

アルゴリズムです。

今回も、実際に過去の試験で出題されたアルゴリズムを用いて、ランダムに並んだ値をマージソートによって昇順に並び替える処理を見ていきたいと思います。

上のアルゴリズムでは、配列が3つ用意されており、入力用のinput[]、出力用のoutput[]、置き換え作業用のtemp[]があり、基本的に、データの置き換えは、output[]とtemp[]の2つの配列を用いて行われていることが確認できます。

例えば、併合対象領域（分割後の1グループあたりのデータ数）の大きさが2で、0,1番目の2つの整数データの大小関係を調べるときには、以下の手順でソートを行います。（各処理文末の数字は上のアルゴリズムに振られた番号と対応）

１　input[0～n]をoutput[0～n]にコピーする。（②）

２　output[0]の整数データをtemp[0]に一時的に格納する。（⑩）

３　temp[0]とoutput[1]とを比較し、temp[0] < output[1]であれば、output[0]にtemp[0]に格納（要するに同じデータを格納するので変化なし）し、temp[0] > output[1]であれば、output[0]にoutput[1]を格納（output[0], [1]のデータが被っている状態になる）する。（⑰ or ㉑）

４　３の前者を行った場合には、output[1]にoutput[1]を格納し（日本語がおかしいが、プログラムの流れに沿うとこうなる。要するに同じデータを格納するので変化なし、output[0] < output[1]の関係も既に成立している。）、２の後者を行った場合には、output[1]にtemp[0]を格納（output[0] < output[1]の関係が成立）する。（⑰ or ㉑）

５　output[2]の整数データをtemp[0]に一時的に格納する。（内側のループ処理後の㉖後の⑩）

・・・最後の配列まで大小関係の比較が終われば、併合対象領域を2倍にし（㉗）、以降、併合対象領域がデータ数となるまで同様にソートを行う。

それでは、実際に以下の配列を用いて、上記のマージソートのプログラムややこれについて説明した手順１～５に沿ってどのように処理がなされるか見てみましょう（ここでは、大まかな流れを説明しますので、細かい処理や各変数の状態を知りたい方は、作成したトレース表を終盤に貼っておりますので参考にしてみてください。）。なお、以下で紹介する配列について、

一番上の行：配列outputの要素番号

真ん中の行：プログラム上の「span_idx」に対応する値

一番下の行：要素の値

とします。

今回も、初めは併合対象領域の大きさを２として、すべての配列を見ていき、併合対象領域が配列の数と同数になるまでソートを行っていきます。

まず、span_idxに0が代入されているので、span_idx=0に該当する要素番号0,1の値の比較を行います。

temp[0](output[0]を代入したもの) > output[1]であることからoutput[0]にoutput[1]を格納（手順３）し、以下のようになります。

output[1]にtemp[0]を格納することで、以下のように、span_idx[0]が昇順になりました。

これと同様の作業をspan_idx[2], [4], [6]にも行い、2要素ごとのグループ内で昇順になるようにソートを行います。今回は、span_idx[6]で入れ替え作業が発生します。

そして、最後の配列まで大小関係の比較が終われば、併合対象領域を2倍にして（上記のプログラム㉗に対応）、各併合対象領域内で大小関係を比較し、必要に応じてソートを行っていきます。

上の配列では、span_idx[4]内が昇順に並んでいないため、ソート処理を行います。

temp[0], [1] に それぞれ、output[4], [5] を代入し（上のプログラム⑨, ⑩に対応）、output[4] , [5] に output[6], [7]を代入します（上のプログラム㉑に対応）。

そして、output[6], [7] にそれぞれ、temp[0], [1] を代入し（上のプログラム⑯に対応）、span_idx[4]内のソートが完了します。

最後に、併合対象領域をさらに2倍して同様の作業を行う流れとなります。

それでは、マージソートの流れを大まかに確認し終えたところで、トレース表も以下に載せておきます。トレース表を見ただけでは、中々分かりづらいと思うので、アルゴリズムの処理や先ほど紹介したソートの流れと合わせて実際にトレースを行い、下のトレース例と見比べて頂ければと思います。

著者：かわ