マージソート — 分割統治法アプローチ

マージソートの動作原理

マージソートは、すべてのケース（最良、平均、最悪）でO(n log n)の時間計算量を達成する古典的な分割統治法アルゴリズムです。配列を再帰的に半分に分割し、各半分をソートし、ソートされた半分をマージして元に戻します。

3つのステップ

1. 分割: 配列を2つの半分に分割
2. 統治: 各半分を再帰的にソート
3. 結合: 2つのソート済み半分を1つのソート済み配列にマージ

function mergeSort(arr, left, right):
  if left >= right: return
  mid = (left + right) / 2
  mergeSort(arr, left, mid)
  mergeSort(arr, mid + 1, right)
  merge(arr, left, mid, right)

マージ手順

マージステップはアルゴリズムの核心です。2つのソート済みサブ配列を取り、各サブ配列から要素を1つずつ比較しながら1つのソート済み配列に結合します：

function merge(arr, left, mid, right):
  一時配列を作成 L = arr[left..mid], R = arr[mid+1..right]
  i = 0, j = 0, k = left
  while i < len(L) and j < len(R):
    if L[i] <= R[j]:
      arr[k] = L[i]; i++
    else:
      arr[k] = R[j]; j++
    k++
  残りの要素をコピー

再帰ツリー

8要素の配列では、再帰ツリーは3レベル（log₂ 8 = 3）です。各レベルですべてのn要素がマージ中に処理されるため、総作業量はn * log nになります。

保証されたO(n log n)

クイックソートとは異なり、マージソートの性能は入力順序に依存しません。分割は常に正確な半分（ピボット選択に依存しない）で行われるため、再帰深度は常にlog nで、各レベルはO(n)の作業を行います。

トレードオフ：空間

マージソートの主な欠点は、マージ中に使用される一時配列のO(n)の追加空間要件です。メモリ制約のある環境には適しません。