マージソート | Programming Place Plus　用語集

名称

• マージソート　【merge sort】
• (同義) 併合ソート　【merge sort】

解説

ソートのアルゴリズムの一種で、ソートされている２つのデータ列をマージ（併合）する作業を繰り返すことによって、ソートを行う手法です。

２つのデータ列がソート済みであれば、それぞれの先頭の要素のうち、小さいもの（あるいは大きいもの）を選べば、そのデータは必ず、全体の中での最小値（あるいは最大値）です。このように選び出したデータを、新しいデータ列へ移動させることを繰り返せば、すべてのデータが新しいデータ列に移動し終えたとき、そのデータ列はソート済みになっています。２つのデータ列を合体させて、新しいデータ列を生み出すことをマージ（併合）と呼び、マージを繰り返し利用することからマージソートと呼ばれます。

ソートすることが目的でありながら、ソート済みのデータ列を用意しなければならないことが矛盾しているようですが、ソート済みのデータ列は、ソートしたいデータ列を分解して作り出します。そのためにまず、ソートしたいデータ列を、データが１つしか含まれないデータ列になるまで２分割していく作業を再帰的に繰り返すことから始めます。完全にばらばらに分解されたら、隣のデータ列とのマージを行い、それを再帰的に繰り返すことでマージソートが完成します。

計算量としては O(n log n) で、対象のデータの並び方に影響されない特徴があります。また、安定ソートとして実装できます（マージの実装を間違えると、安定ソートにならない）。

２つのデータ列を１つのデータにマージする作業をおこなうため、ソート対象が配列の場合、同サイズの追加のメモリ領域が必要となることが欠点とされます。

マージソートの解説がアルゴリズムとデータ構造編【整列】第７章にあります。