マージソートをトレースしてみる
マージソートとは、
大量のデータをいくつかのグループに分割し、整列と併合を行う
アルゴリズムです。
今回も、実際に過去の試験で出題されたアルゴリズムを用いて、ランダムに並んだ値をマージソートによって昇順に並び替える処理を見ていきたいと思います。
上のアルゴリズムでは、配列が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倍して同様の作業を行う流れとなります。
それでは、マージソートの流れを大まかに確認し終えたところで、トレース表も以下に載せておきます。トレース表を見ただけでは、中々分かりづらいと思うので、アルゴリズムの処理や先ほど紹介したソートの流れと合わせて実際にトレースを行い、下のトレース例と見比べて頂ければと思います。
著者：かわ