(7.1.1) マージ (merge) ソートでは， ソートすべきデータがはいっている配列 a[ ] のほかにそれと同じ大きさの配列 b[ ] が必要となるのが欠点であるが， アルゴリズムは比較的わかりやすい。
(7.1.2) 配列 a[ ] が次を満たしているとする。
これを（ここでは）「4 ずつ並んでいる」と呼ぼう。 （最後に半端が出たら，それらも小さい順に並んでいるとする。）
(7.1.3) このとき，この配列全体をもう一つの配列 b[ ] にコピーし， 次を満たしているようにする。
(7.1.4) 子どもたちが四人ずつ班に別れ， それぞれの班の中では背の順に並んでいるとき， 二班を一つにまとめ，八人が背の順に並ぶようにせよ，というのと同じである。
(7.1.5) それには，次のようにすればよい。 a[1] から a[8] までの部分で説明しよう。 まず a[1] と a[5] を比べ，小さいほうを b[1] にコピーする。 もしも a[1] のほうがコピーされたなら， 次には a[2] と a[5] を比較する。 いわば“勝ち抜き戦”である。 片方のグループの元をすべてコピーしてしまったら， あとはもう一つのグループの残りを（比較することなしに）順にコピーする。
(7.1.6) 配列 a[ ] 全体に対し上の操作を行なって配列 b[ ] にコピーし終えたら， それから，b[ ] 全体を a[ ] に， そっくりそのまま，順序を変えずにコピーする。
(7.1.7) これで，「4 ずつ並んでいる」から 「8 ずつ並んでいる」に変えることができた。
(7.1.8) 最初に配列 a[ ] を乱数で初期化した直後には， この配列は「1 ずつ並んでいる」と言える。 それを上のような操作で「2 ずつ並んでいる」ように変え， 「4 ずつ並んでいる」ように変え， ……としてゆけば，やがて配列全体がソートされる。 このアルゴリズムを「マージソート」という。
(7.1.9) m ずつ並んでいる m 個のもの二組を小さい順に並べて別の場所にコピーする際， 次にコピーすべき元（げん）を決めるには，たかだか一回の比較で済む。 最後の一つは，残ったものだから，比較しなくても決まる。 よって，比較回数はたかだか 2m-1 回である。 コピーされる元は 2m 個である。 これらは Ο(m) である。 よって， 「m ずつ並んでいる」から「2m ずつ並んでいる」に変えることは Ο(N) の計算量で可能である。 これを全部で約 log2(N) 回くりかえすから， 全体では Ο(N log(N)) である。
(7.2.1) マージソートのプログラムを書き，挿入ソートと同様の実験を行ない， レポートせよ。
(7.2.2) 挿入ソートのソースファイルをコピーしたものから挿入ソートの二重ループを削除し， 下のプログラムをはりつけ，ヒントに従って埋めてゆく。 ファイル名は merge.c がよいだろう。
(7.2.3) プログラムの main() は次のようになる。
変数は，次のように，五つ用意する。
main() {
int m, start, i, j, k;
/* ここで，前のように，配列の大きさの表示，配列 */
/* の初期化，初期化直後の配列の画面表示を行なう */
for (m = 1; m ???; m = ???) {
printf("「%d ずつ並んでいる」のを", m);
printf("「%d ずつ並んでいる」ように変えます.\n", 2*m);
for (start = 1; start ???; start = ???) {
i = 0; j = 0; k = 0;
for ( ; ????????????????????????????????; ) {
if (a[start+i] < a[start+m+j]) {
b[???] = a[???];
} else {
b[???] = a[???];
}
}
for ( ; ??????????????????????; ) {
b[???] = a[???];
}
for ( ; ??????????????????????; ) {
b[???] = a[???];
}
}
/* ここで，for ループを用いて，配列 b[ ] を a[ ] に */
/* そっくりそのままコピーする */
print();
}
/* ここで比較回数の表示などを行なう（オプション） */
}
(7.2.4) 「int a[N+1];」の次の行に「int b[N+1];」を入れるのを忘れずに。
(7.2.5) N の大きさを 50000000, 100000000, 200000000 とし， それぞれについて，五回の実験を行ない， かかった時間の平均を求めよ。 時刻の差や，時間の平均は，手計算か電卓で求めよ。
(7.2.6) また， 挿入ソートでこれだけの大きさのデータをソートしたらどれだけの時間がかかるか， 課題１の結果をもとに計算せよ。
(7.2.7) メールは，必ず，この授業で配布したアカウントから送れ。 メールの本文冒頭に， 学籍番号，名列番号，氏名（として大学に届けてあるもの）を忘れずに書け。 次に，レポートの内容を，「マージソートのプログラムと実験結果」程度に， 簡潔に書け。
(7.2.8) その次に，プログラムを載せよ。 その際，Active! mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。 そのプログラムは，実験を行なったプログラムそのものでなければならない。 （一部でも変更したときは，コンパイル・実行をやり直すこと。）
(7.2.9) 五回の実験結果をまとめてコピペせよ。 すなわち，プロンプトや 「date; ./a.out; date」を含んだままコピペせよ。 （編集すると間違うおそれがあるため。）
(7.2.10) そのあとに，各回にかかった時間と，平均を書け。 「25, 26, 24, 26, 25 秒で平均は 25.2 秒。」のように。
(7.2.11) 宛て先は私（岩瀬）の実習用アカウント（(1.9.7) 参照）である。 件名は「?? kadai2」（←全て半角文字，小文字， ?? は自分の id の下二けた，その後ろに半角スペース一つ， kadai と 2 の間にはスペースを入れない）とせよ。
(7.3.1) この節は，課題が早く終わって時間が余った人のためのものである。 前に (5.1.3) で述べた， ソート前のデータに同じ値のものがあった場合の問題を考えよう。
(7.3.2) あるソートのアルゴリズムが「安定 (stable)」であるとは， 同じ値のものが，ソート後も元の順序を保っていることをいう。 あるソートアルゴリズムが安定であることをいうには， 数学の定理と同様に証明が必要であり， 不安定（あるいは非安定）であることをいうには反例をもって示すべきであるが， 実験で試し，その結果を参考にすることができる。
(7.3.3) この授業で書いているプログラムを少し改変することで， その実験が行なえる。以下では，そのやり方の一つを説明する。 プログラムのコピーを，次のように改変する。
(7.3.4) 以上のように改変してから実行する。 ソート後，a[i] の値が同じものが並んだら， それらの中で b[i] の値が小さい順かどうかを調べる。
(7.3.5) 配列の大きさ N を画面の一行に収まるぐらいとし， 途中の過程をすべて出力させて実験すれば， どの過程で安定性が崩れるのかをも見ることができる。
(7.3.6) 配列の大きさを大きくして試したい場合， 安定かどうかを目で見て判定するのは大変であろう。 print() は呼ばないようにし， main() の最後に安定かどうかをチェックする部分をつけるとよい。 a[i] と a[i+1] が等しいときに b[i] と b[i+1] の大小関係を調べればよいだろう。
(7.3.7) この授業の課題では， 同じ値をもつものはないと考えてプログラムを書いてきた。 そのため， a[i] > a[i+1] のように， 等号なしの不等号を用いたであろう。 そこを， 等号つきの不等号で置き換えても正しいプログラムであるかどうか確認せよ。 正しいならば，そのプログラムでも実験を行ない， 等号なしの場合と比べて，実行時間，比較・交換回数が変わるか調べてみよ。 その際には，同じ値をもつものが多くあるほうが違いがわかりやすいので， N の値を大きくし，かつ， 初期化は a[i] = rand() % 99 + 1; などとするのもよい。