マージソートの仕組み

マージソートは、小さい順に並んだ複数のまとまりを2つずつ統合していく方法です。このまとまりを部分列と呼びます。最初に配列の要素を1つずつに分けます。要素が1つだけなら、それだけで小さい順に並んでいると考えられます。統合するときは両方の先頭を比べ、小さい方を1つずつ取り出します。この統合を繰り返し、部分列が1つになると配列全体が整列されています。