マージソート【merge sorting】併合ソート/併合整列法

概要

マージソートとは、データ列を一定の順序に並べ替えるソート（整列）アルゴリズムの一つで、データ列を要素単位まで再帰的に分割し、整列しながら少しずつ併合（マージ）していく手法。分割統治法に基づくアルゴリズムとして知られる。

まず、対象のデータ列をほぼ半分ずつに分割し、さらにその半分へと、各部分列が単体（ただ一つの要素）になるまで分割を繰り返す。1要素の列はそれ自体が整列済みとみなせるため、次の併合段階へ移る。

併合では、隣り合う整列済みの部分列の先頭要素同士を比較し、条件を満たす方（昇順であれば小さい方）を取り出して新しい列に追加する。どちらかの列が空になるまでこれを繰り返し、残った要素をそのまま末尾に追加することで整列済みの列が得られる。この操作を段階的に繰り返し、全要素が一つの列にまとまった時点で整列が完了する。

計算量は平均・最悪いずれの場合も O（n log n）であり、入力データの初期状態による性能のばらつきがない。最悪計算時間が O（n²）に劣化する場合があるクイックソートと比べ、処理時間の上限を予測しやすく、大規模データの処理に向いている。

併合の過程で元のデータ列とは別に O（n）程度の作業用の記憶領域が必要となり、メモリ容量に制約がある環境では不利となる。また、実装上の工夫により同順位の要素の順番が入れ替わらない安定ソートとすることができる。作業領域は不要だが不安定ソートであるクイックソートとは対象的なソート法である。

(2026.6.30更新)