(55.1) これは、課題が早く終わってしまった人のためのオプション項目である。
(55.2) 配列 a[ ] が
(55.3) このとき、この配列全体をもう一つの配列 b[ ] にコピーし、
(55.4) これで、 「4 つずつ並んでいる」から 「8 つずつ並んでいる」に変えることができた。
(55.5) 最初に配列 a[ ] を乱数で初期化した直後には、 この配列は「1 つずつ並んでいる」と言える。 それを上のような操作で「2 つずつ並んでいる」ように変え、 「4 つずつ並んでいる」ように変え、 ……とくりかえしてゆけば、やがて配列全体がソートされる。 このアルゴリズムを「マージソート」という。
(55.6) 各ステップの計算量は Ο(N) であり、 全部で log(N) ステップだから、 全体では Ο(N log(N)) のアルゴリズムである。 ヒープソートと同じオーダーだが、アルゴリズムはわかりやすい。 ただし、 ソートする配列と同じ大きさの配列をもう一つ用意する必要があるのが欠点である。
(55.7) このアルゴリズムについて、前の課題と同じようなことを調べてみよ。 （いままでのアルゴリズムとは異なり、 要素の交換のくり返しではないから、 関数 swap() は使わない。 よって、交換回数は調べない。）
(55.8) ※ 「a[1] から a[4] まで」 「a[5] から a[8] まで」が小さい順に並んでいるとき、 これらを 「b[1] から b[8] まで」に小さい順にコピーする際には、 まず a[1] と a[5] を比べて小さいほうを b[1] にコピーする。 もしも a[1] のほうがコピーされたなら、 次には a[2] と a[5] を比較する。 いわば“勝ち抜き戦”である。 片方のグループの元をすべてコピーしてしまったら、 あとはもう一つのグループの残りを（比較することなしに）コピーする。
(55.9) ※ 配列の大きさは 2 のベキとは限らないので、 半端の扱いがちょっと面倒かもしれない。
(55.10) ※ 実は、b[ ] 全体を a[ ] にコピーするのは無駄であり、 次のステップでは逆に b[ ] から a[ ] にコピーするようにすればこの無駄は省ける。 しかし、プログラムが煩雑になるか、まだ習っていない書き方が必要になる（と思う）。