マージソート

あらかじめ整列してある2つの配列を合体させて、新しい、整列された配列を得るのは容易です。マージソートはこれに着目して、並べ替えたい配列を再帰的に分割していき、再び併合（マージ）していくことで、並び替えを実現しようとする、ソートアルゴリズムです。 次の図は、マージソートが行われる過程を表しています。 ばらばらな順番で与えられた配列データは、まず始めに小さい配列へと分解されます。このとき、マージソートでは各配列がほぼ2分割されるように分解していきます。 もっとも小さい配列（要素数1）まで分解されたら、それを順序良く併合していきます。このとき、2つの配列の先頭から小さい方を取り出して新しい配列を作成するようにすれば、取り出すだけで整列された配列を作成することができます。 /* * マージ * 2つの配列a1[]とa2[]を併合してa[]を作ります。 */ void merge(int[] a1,