過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

マージソート

分けてから順序を保って併合する

マージソートは、データを部分に分け、それぞれを整列し、整列済みの列を併合して全体を整列する方法です。マージは併合を意味します。二つに分ける方式では、要素が一つになるまで分割し、戻りながらまとめる考え方が基本です。クイックソートと同じ分割統治法でも、分割と統合の役割が異なります。

併合の手順

整列済みの列Aが1、4、8、列Bが2、3、9なら、それぞれの先頭を比較します。小さい方を結果へ移し、その列の次の要素を比較に使います。一方が空になったら、もう一方の残りを順に加えます。既に各列の順序がそろっているため、毎回全要素の最小値を探し直す必要はありません。

Pythonによる併合例

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result + left[i:] + right[j:]

等しい値では左側を先に選ぶことで、元の順序を保つ構成にできます。

計算量と領域

二分割する標準的な方法では段数が対数的になり、各段で合計n個程度を併合するため、時間計算量はO(n log n)です。配列を使う一般的な実装では補助領域が必要になります。連結リストで参照をつなぎ直す方式などでは、領域の扱いが異なるため、実装の前提を確認します。

利用場面と試験

安定性が必要な整列や、記憶装置上の大きなデータを部分ごとに処理する外部整列で、併合の考え方が役立ちます。試験では、分割した直後と併合後の配列を区別します。整列済みの二列の併合は全体のソートより単純な操作です。クイックソートのピボットによる分割と、マージソートの整列済み部分を合わせる処理を対比すると、アルゴリズムの流れを見分けやすくなります。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

用語一覧

2件