DSA Interview Prep · レッスン

マージソート：分割、整列、マージ

Q: 「マージソート：分割、整列、マージ」レッスンは無料ですか？

はい。「マージソート：分割、整列、マージ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。

Q: DSA Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

Q: 「マージソート：分割、整列、マージ」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このDSA Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

マージソートを再帰的に実装し、分割統治の木を追跡し、あらゆるケースでO(n log n)を保証できる理由を説明します。

「マージソート：分割、整列、マージ」はCoddyKit上の無料DSA Interview Prepレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。

分割統治法の考え方

マージソートは典型的な分割統治アルゴリズムです。配列を半分に分割し、それぞれを再帰的にソートしてから、2つのソート済みの半分を1つのソート済みの結果にマージします。2つのソート済み配列のマージはO(n)で行えるため、最初からソートするよりはるかに低コストであるという点が重要です。この分解により、log n段の再帰木ができ、各段でO(n)のマージ処理が必要になります。その結果、比較ソートにおける最適な計算量の下限であるO(n log n)が得られます。

# High-level merge sort structure
def merge_sort(arr):
    # Base case: 0 or 1 element already sorted
    if len(arr) <= 1:
        return arr
    # Divide
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])   # sort left half
    right = merge_sort(arr[mid:])   # sort right half
    # Conquer (merge)
    return merge(left, right)

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

マージステップの説明

2つのソート済み配列をマージするには、それぞれの半分に1つずつ、2つのポインタを用意します。先頭の要素を比較し、小さい方を出力にコピーして、そのポインタを進めます。一方の半分が尽きたら、もう一方の残りをそのままコピーします。出力配列にO(n)時間とO(n)空間が必要です。マージステップはマージソートのアルゴリズム上の核心なので、深く理解してください。

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= preserves stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]

マージソートの完全な実装

分割とマージを組み合わせます。再帰呼び出しによって、要素が1つだけになる（自明にソート済みになる）まで問題を半分に分割し、その後、マージ呼び出しによって再び結合します。再帰木の各レベルでは、複数のマージに分散されながらも、合計で同じ n 個の要素をマージします。再帰の深さは log₂(n) なので、全体の時間計算量は O(n log n) です。マージの出力配列に O(n) の補助領域が必要で、さらに呼び出しスタックの深さに O(log n) が必要です。

def merge_sort_full(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort_full(arr[:mid])
    right = merge_sort_full(arr[mid:])
    # Merge the two sorted halves
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]: merged.append(left[i]);  i += 1
        else:                   merged.append(right[j]); j += 1
    merged.extend(left[i:] + right[j:])
    return merged

print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]

マージソートの再帰木

n=8 のマージソートの再帰木を見てみましょう。レベル0には8要素の配列が1つ、レベル1には4要素の配列が2つ、レベル2には2要素の配列が4つ、レベル3には要素が1つずつの配列が8つ（ベースケース）あります。上に戻ると、レベル3→2では合計8要素、レベル2→1でも合計8要素、レベル1→0でも合計8要素をマージします。つまり、3レベル × 8要素 = 24回の操作 ≈ 8 × log₂(8) = 24 です。これにより O(n log n) であることが確認できます。

# Trace the tree depth
level_work = []

def merge_sort_traced(arr, depth=0):
    if depth >= len(level_work):
        level_work.append(0)
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort_traced(arr[:mid],  depth+1)
    right = merge_sort_traced(arr[mid:],  depth+1)
    level_work[depth] += len(arr)  # track merge work
    merged = sorted(left + right)  # simplified merge
    return merged

merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
    print(f'Level {d}: {work} elements merged')

インプレース・マージソート

標準的な再帰的マージソートでは、マージ結果の出力に O(n) の補助領域を割り当てます。インプレースでマージするマージソートも存在しますが、複雑で定数倍のコストも大きいため、面接で問われることはほとんどありません。面接でよくある追加質問は、「マージソートを追加領域 O(1) で実行できますか？」です。正しい答えは、「理論上は可能ですが、実用的な実装では O(n) の領域を使うか、複雑さを増やす必要があります。Python の Timsort はマージに O(n) の領域を使います」です。

# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
    n = len(arr)
    width = 1
    while width < n:
        for i in range(0, n, 2 * width):
            left  = arr[i:i+width]
            right = arr[i+width:i+2*width]
            # Merge and put back
            merged = []
            a, b = 0, 0
            while a < len(left) and b < len(right):
                if left[a] <= right[b]: merged.append(left[a]);  a+=1
                else:                   merged.append(right[b]); b+=1
            merged += left[a:] + right[b:]
            arr[i:i+len(merged)] = merged
        width *= 2
    return arr

print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]

マージソートは安定ソート

マージソートは安定です。マージ後の出力では、左半分にある等しい要素が、右半分にある等しい要素より必ず前に現れます。これは、左側の要素を優先するときに <=（<ではなく）を使うことで保証されます。安定性は複数キーでのソートで重要です。Python 組み込みの sorted() と list.sort() は、同じく安定で O(n log n) の Timsort を使うため、本番コードでは常に安全な選択肢です。

# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items)  # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)

K個のソート済み配列をマージする

合計 n 個の要素を持つ k 個のソート済み配列は、ペアを繰り返しマージすることで（トーナメント表のように）O(n log k) 時間でマージできます。各マージレベルで n 個の要素を処理し、レベル数は log k です。別の方法として、サイズ k のミニヒープを使うこともできます。各配列から残っている最小要素をヒープに追加し、最小要素を取り出して、その配列の次の要素を追加します。このヒープを使う方法も O(n log k) ですが、k が非常に大きい場合はよりメモリ効率に優れています。

import heapq

def merge_k_sorted(arrays):
    result = []
    heap = []
    # Push first element from each array with array index
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    while heap:
        val, arr_i, elem_i = heapq.heappop(heap)
        result.append(val)
        if elem_i + 1 < len(arrays[arr_i]):
            next_val = arrays[arr_i][elem_i + 1]
            heapq.heappush(heap, (next_val, arr_i, elem_i+1))
    return result

arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs))  # [1,2,3,4,5,6,7,8,9]

マージソートで転倒数を数える

転倒（a[i] > a[j] かつ i < j となるペア）を O(n log n) で数えるには、マージソートを変更して使います。マージ中に、右側の部分配列の要素が左側の部分配列の要素より小さい場合、その要素は左側の部分配列に残っているすべての要素と転倒を形成します。その時点で個数に len(left) - i を加えます。

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left,  l_inv = count_inversions(arr[:mid])
    right, r_inv = count_inversions(arr[mid:])
    merged = []
    inversions = l_inv + r_inv
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            inversions += len(left) - i  # all remaining left elements > right[j]
    merged.extend(left[i:] + right[j:])
    return merged, inversions

_, inv = count_inversions([3, 1, 2])
print(inv)  # 2: (3,1) and (3,2)

マージソートとクイックソートの比較

マージソートはすべての場合で O(n log n) を保証し、安定であり、連結リストや外部ソートに適しています。クイックソートは平均計算量が O(n log n) ですが、最悪計算量は O(n²) です。インプレースで実行でき（スタック領域は O(log n)）、配列上でのキャッシュ効率が高いため、実際にはより高速なことが多くあります。Python 組み込みのソートは Timsort（マージソートの派生）を使うため、常にデフォルトとして適切な選択です。

# Head-to-head complexity comparison:
# Algorithm     | Best  | Avg      | Worst  | Space  | Stable
# Bubble sort   | O(n)  | O(n^2)   | O(n^2) | O(1)   | Yes
# Insertion sort| O(n)  | O(n^2)   | O(n^2) | O(1)   | Yes
# Merge sort    | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort    | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort     | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No

print('Merge sort: stable, O(n log n) guaranteed, O(n) space')

外部ソート：大規模データでのマージソート

マージソートは外部ソート（RAM に収まらない大きさのデータをソートする処理）を支えるアルゴリズムです。データをチャンク単位で読み込み、各チャンクをメモリ上でソートしてから、ディスク上でチャンクをマージします。マージ処理では、各ソート済みランから一度に1要素ずつ読み込み、メモリ上には一度に O(k) 個の要素（各ランにつき1個）だけを保持します。このため、マージソートはデータベース、Hadoop MapReduce、従来のテープソートアルゴリズムで使われています。

# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
    chunks = []
    for i in range(0, len(data), chunk_size):
        chunk = sorted(data[i:i+chunk_size])  # sort in-memory
        chunks.append(chunk)
    print(f'Created {len(chunks)} sorted chunks')
    # Merge all chunks
    import heapq
    heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
    heapq.heapify(heap)
    result = []
    while heap:
        val, ci, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(chunks[ci]):
            heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
    return result

print(external_sort(list(range(20,0,-1)), 5)[:10])

マージソートのまとめと面接のポイント

面接では、マージソートをきれいに実装することで、再帰、マージ処理、分割統治への理解を示せます。よくある追加質問は次のとおりです。

なぜ O(n log n) で、O(n²) ではないのですか？（log n レベル × 各レベルで n の処理）
安定ソートですか？（はい、マージで <= を使います）
必要な領域はどのくらいですか？（O(n) の補助領域 + O(log n) のスタック）
反復的に実装できますか？（はい、ボトムアップ・マージソートを使えます）
連結リストではどのように使いますか？（配列より簡単です。O(n) のスライスコストがなく、slow-fast で中央点を見つけます）

# One-shot merge sort for interview clarity:
def ms(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: res.append(l[i]); i+=1
        else:             res.append(r[j]); j+=1
    return res + l[i:] + r[j:]

print(ms([5,2,4,6,1,3]))  # [1,2,3,4,5,6]

理解度チェック

このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。

レッスンの振り返り

このレッスンでは、マージソートは配列を中央で分割し、それぞれの半分を再帰的にソートしてから、ソート済みの2つの半分を O(n) でマージします。これにより、log n 個の再帰レベル全体での実行時間は O(n log n) になります。また、マージ処理では同値の場合に左側の要素を選ぶために <= を使い、安定性を保証します。さらに、マージソートは連結リスト、外部ソート、安定性が必要な場合に適したアルゴリズムです。一方、領域が限られている場合、メモリ上の配列にはクイックソートが適しています。次はクイックソートを実装し、ピボット選択戦略を詳しく見ていきます。

よくある質問