マージソートの仕組み・コード・計算量をわかりやすく解説

考え方を平易に説明

要素が0個または1個のリストは、すでにソート済みです。それより長いリストでは次のようにします。

1. 分割：リストを左半分と右半分に分けます。
2. 統治：それぞれの半分をマージソートでソートします。
3. 結合：ソート済みの2つの半分をマージします。それぞれの先頭の要素を比べて小さいほうを出力に移す、という操作を片方が空になるまで繰り返し、その後、もう一方の残りをコピーします。

実際の作業はすべてマージの手順で行われます。全体の長さが n の2つのソート済みリストをマージするのに必要な比較は、最大でも n − 1 回です。

具体例をステップごとに見る

[38, 27, 43, 3, 9, 82, 10] をソートします。

最後のマージでは先頭同士を比較します。27 と 3 では 3、27 と 9 では 9、27 と 10 では 10、27 と 82 では 27、38 と 82 では 38、43 と 82 では 43 を取り、最後に 82 をコピーします。7要素に対して比較は6回です。

Pythonでの実装

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= takes from left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one of these is empty
    out.extend(right[j:])
    return out
def merge_sort(items):
    """Return a new sorted list."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # []

このトップダウン版は明快ですが、スライスをコピーします。ボトムアップ版なら再帰をまったく使いません。幅 1、次に 2、次に 4 と、ランを順にマージしていきます。

def merge_sort_bottom_up(items):
    a = list(items)
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, lo + 2 * width
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

ボトムアップ版は、上の merge を再利用します。標準ライブラリには heapq.merge もあり、任意の数のソート済みイテラブルを遅延評価でマージできます。

時間計算量と空間計算量

漸化式は T(n) = 2T(n/2) + O(n) です。再帰木の各段階の作業量は合計で O(n)、段階数は約 log₂ n なので、全体で O(n log n) になります。100万件なら約20段階です。

マージソートと他のソートの比較

マージソートが安定なのは、2つの要素が等しいときにマージが左の半分から取るため、等しい要素が順序を保つからです。クイックソートと比べると、最悪ケースでも O(n log n) が保証されますが、O(n) の追加メモリが必要で、配列では通常データの移動も多くなります。ヒープソートと比べると、安定で、メモリに順番にアクセスするため、キャッシュやディスクと相性が良いです。

派生と、よくある間違い

• 自然マージソートは、すでにソート済みのランを検出してマージするため、ソート済みの入力では O(n) になります。Timsort は自然マージソートを洗練させたもので、短いランには二分挿入ソートを使います。
• 小さな部分リスト（たとえば10〜30要素未満）では挿入ソートに切り替えて、オーバーヘッドを減らします。
• 連結リストでは、マージソートに追加のバッファは不要です。マージはノードのつなぎ替えだけで済むため、連結リストのソートでは通常これが選ばれます。
• 外部マージソートは、メモリに収まるチャンクをソートしてディスクに書き出し、その後 k 路マージを行います。データベースや GNU sort などのツールが、大きなファイルに対してこの考え方を使っています。
• 転倒数の数え上げ：マージの途中で、右半分から要素を取り出すたびに、その要素は左半分の残りのすべての要素より小さいことになります。

マージソートを使う場面

安定ソートで、しかも O(n log n) の時間が保証されている必要がある場合、連結リストをソートする場合、データがメモリに収まらない場合に、マージソートを選びます。Pythonでは、単に sorted() か list.sort() を呼べば済みます。これらはマージソートの派生である Timsort を実装しているので、すでにこれらの性質が得られます。マージソートを手で書くのは面接の定番課題で、転倒数の数え上げや、k 個のソート済みリストのマージに発展することがよくあります。