(10.1.1) マージ (merge) ソートは，アルゴリズムは比較的わかりやすいが， ソートすべきデータがはいっている配列 a[ ] のほかに， それと同じ大きさの配列 b[ ] が必要となる。 （最近のコンピュータは大量のメモリーを搭載しているので， この点はあまり問題にならないように思う。）
(10.1.2) 配列 a[ ] が次を満たしているとする。
これを（ここでは）「4 ずつ並んでいる」と呼ぼう。 （最後に半端が出たら，それらも小さい順に並んでいるとする。）
(10.1.3) このとき，この配列全体をもう一つの配列 b[ ] にコピーし， 次を満たしているようにする。
(10.1.4) 子どもたちが四人ずつ班に別れ， それぞれの班の中では背の順に並んでいるとき， 二班を一つにまとめ，八人が背の順に並ぶようにせよ，というのと同じである。
(10.1.5) それには，次のようにすればよい。 a[1] から a[8] までの部分で説明しよう。 まず a[1] と a[5] を比べ，小さいほうを b[1] にコピーする。 もしも a[1] のほうがコピーされたなら， 次には a[2] と a[5] を比較する。 いわば“勝ち抜き戦”である。 片方のグループの元をすべてコピーしてしまったら， あとはもう一つのグループの残りを（比較することなしに）順にコピーする。
(10.1.6) 配列 a[ ] 全体に対し上の操作をおこなって配列 b[ ] にコピーし終えたら， それから，b[ ] 全体を a[ ] に， そっくりそのまま，順序を変えずにコピーする。
(10.1.7) これで，配列 a[ ] を， 「4 ずつ並んでいる」から 「8 ずつ並んでいる」に変えることができた。
(10.1.8) 最初に配列 a[ ] を乱数で初期化した直後には， この配列は「1 ずつ並んでいる」と言える。 それを上のような操作で「2 ずつ並んでいる」ように変え， 「4 ずつ並んでいる」ように変え， ……とくりかえしてゆけば，やがて配列全体がソートされる。 このアルゴリズムを「マージソート」という。
(10.1.9) m ずつ並んでいる m 個のもの二組を小さい順に並べて別の場所にコピーする際， 次にコピーすべき元（げん）を決めるには，たかだか一回の比較で済む。 最後の一つは，残ったものだから，比較しなくても決まる。 よって，比較回数はたかだか 2m-1 回である。 コピーされる元は 2m 個である。 これらはおよそ 2m である。 よって， 「m ずつ並んでいる」から「2m ずつ並んでいる」に変えることは およそ N の計算量で可能である。 これを全部で約 log2(N) 回くりかえすから， 全体では N log(N) である。
(10.1.10) 最後にとりあげるクイックソートとは異なり， 初めに配列がどのように初期化されていても，このオーダーである。 また，乱数で初期化する場合，平均すると， クイックソートよりも比較回数は少ないようである。
(10.2.1) 課題１と同様のことを，マージソートについておこなえ。
(10.2.2) 挿入ソートのソースファイルをコピーしたものの main() を， 下のプログラムのヒントに従って書き換えてゆく。 ファイル名は merge.c がよいだろう。
(10.2.3) プログラムの main() は次のようになる。
int 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 (comp(start+i, start+m+j) < 0) {
b[???] = a[???];
} else {
b[???] = a[???];
}
}
for ( ; ??????????????????????; ) {
b[???] = a[???];
}
for ( ; ??????????????????????; ) {
b[???] = a[???];
}
}
/* ここで，for ループを用いて，配列 b[ ] を */
/* 配列 a[ ] にそっくりそのままコピーする */
print();
}
/* ここで，いつものように比較回数の表示などをおこなう */
}
変数は，上のように，五つ用意する。
(10.2.4) 「int a[N+1];」の次の行に「int b[N+1];」を入れるのを忘れずに。
(10.2.5) ※ 実は，b[ ] をそのまま a[ ] にコピーして戻すのは時間の無駄である。 その際，ついでに「2m ずつ並んでいる」のを 「4m ずつ並んでいる」ように変えれば， この無駄が省ける。 しかし，プログラムが長くなるか，まだ習っていない書き方が必要になる（と思う）。
(10.2.6) いままでのアルゴリズムとは異なり，要素の交換のくり返しではないから， 関数 swap() は使わない。よって，交換回数は調べない。 （関数 swap() や変数 scount は使わないが，残しておいて構わない。）
(10.2.7) プログラムを書いている間は， 配列の大きさ N を 12, 13, 14, 15, 16 など，いろいろに変えて試すこと。 半端の処理もきちんとできているか，の確認のためである。
(10.2.8) 件名は「?? kadai4」（「??」は自分のアカウント名の下二桁。 全て半角文字，アルファベットは小文字。 kadai と 4 の間にはスペースをいれない）とせよ。 これ以外の注意点は課題１と同じ。
(10.2.9) N の値を大きくしての実験は， N を 10000, 100000, 1000000 にして，五回ずつおこなえ。
(10.2.10) 付記： a[i] を b[j] にコピーする関数 void copy(int j, int i) を作り，その中でカウンタを増やすことでコピーの回数を調べることもできるが， コピーの回数は N の大きさで決まる定数になる。考えてみよ。 なお，上のプログラムでは，配列 b[ ] から配列 a[ ] へのコピーもあるので，実際のコピーの回数はその 2 倍である。 （関数 swap() を使う場合，その中で 3 回のコピーをおこなっているので， コピーの回数は交換回数の 3 倍である。）
(10.3.1) この節は，課題が早く終わって時間が余った人のためのものである。 前に (5.3.3) で述べた， ソート前のデータに同じ値のものがあった場合の問題を考えよう。
(10.3.2) あるソートのアルゴリズムが「安定 (stable)」であるとは， 同じ値のものが，ソート後も元の順序を保っていることをいう。 あるソートアルゴリズムが安定であることをいうには， 数学の定理と同様に証明が必要であり， 不安定（あるいは非安定）であることをいうには反例をもって示すべきであるが， 実験で試し，その結果を参考にすることができる。
(10.3.3) この授業で書いているプログラムを少し改変することで， その実験がおこなえる。以下では，そのやり方の一つを説明する。 プログラムのコピーを，次のように改変する。
(10.3.4) 以上のように改変してから実行する。 ソート後，a[i] の値が同じものが並んだら， それらの中で b[i] の値が小さい順かどうかを調べる。