マージソートはどのように機能しますか？

Question

マージソートはどのように機能しますか？

Accepted Answer

**マージソート**は**分割統治型**、**安定な**ソート方式で、保証された**O(n log n)**の時間で実行されます。配列を半分に分割し、各半分を再帰的にソートしてから、2つのソート済み半分をマージします。

## 考え方

単一の要素は既にソートされています（基本ケース）。2つのソート済みリストのマージは線形であり、log n レベルのマージを行います。

## 例

```python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # sort left half
    right = merge_sort(arr[mid:])     # sort right half
    return merge(left, right)

def merge(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:              # <= keeps it stable
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:]); result.extend(b[j:])
    return result

merge_sort([5, 2, 4, 1, 3])           # -> [1, 2, 3, 4, 5]
```

## 計算量

- **時間:** O(n log n) *すべての*ケース（最良、平均、最悪）。
- **空間:** マージバッファ用に O(n)（インプレースではない）。

## 使用時期 / 注意点

**安定性**または保証された O(n log n) が必要な場合、および**リンクリスト**と巨大ファイルの**外部ソート**に最適です。追加の O(n) メモリが主な欠点です。

## なぜ重要なのか

マージソートは入力に関わらず O(n log n) を保証します。クイックソートの O(n²) 最悪ケースと異なります。

その安定性は同じキーの相対的な順序を保持し、マルチキーソートで重要です。

マージステップは再利用可能なプリミティブであり、分割統治構造はいたるところで再利用するテンプレートです。