ソートアルゴリズム ── 比較ソートの下限と実用ソートの戦略
扱う概念：比較ソートの理論下限 O(n log n)、QuickSort、MergeSort、Timsort、安定性、非比較ソート（Counting/Radix）
この章で何ができるようになるか：各ソートアルゴリズムの特性を比較して場面に応じた選択ができ、「なぜ比較ソートは O(n log n) より速くならないか」を説明できる。
比較ソートの理論下限
n 個の要素の順列は n! 通り。比較1回で候補を半分に絞れるとして、全てを区別するには log₂(n!) 回の比較が必要。
スターリングの近似: log₂(n!) ≈ n log₂(n) - n log₂(e) = Ω(n log n)
→ 比較ベースのソートは O(n log n) より速くならないQuickSort
平均 O(n log n)、最悪 O(n²)。実際には最も高速なソートの1つ。
def quicksort(arr: list, lo: int = 0, hi: int = None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
pivot_idx = partition(arr, lo, hi)
quicksort(arr, lo, pivot_idx - 1)
quicksort(arr, pivot_idx + 1, hi)
def partition(arr, lo, hi) -> int:
"""Lomuto partition: ピボットを末尾に置く"""
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i最悪ケースの回避：既にソート済みの配列で最悪 O(n²) になる。対策：
- ランダムなピボット選択
- 中央値の中央値（Median of Medians）
import random
def partition_random(arr, lo, hi) -> int:
rand_idx = random.randint(lo, hi)
arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx] # ランダムをピボットに
return partition(arr, lo, hi)MergeSort
常に O(n log n)。安定。追加メモリ O(n)。
def merge_sort(arr: list) -> list:
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left: list, right: list) -> list:
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
result.extend(left[i:])
result.extend(right[j:])
return resultTimsort：Python / Java が採用する実用ソート
Tim Peters が2002年に開発。MergeSort + InsertionSort のハイブリッド。
Timsort の戦略:
1. 配列を「run」と呼ばれる自然に昇順/降順な連続部分に分割
2. 短い run は Insertion Sort で整える（小さい配列では高速）
3. run 同士を MergeSort でマージ
なぜ速いか:
- 「ほぼソート済み」データに対して O(n) に近い
- キャッシュ効率が良い（連続メモリへのアクセスが多い）
- 安定（同じ値の順序が保たれる）
計算量:
最良: O(n)（既にソート済み）
平均: O(n log n)
最悪: O(n log n)
空間: O(n)ソートの安定性（Stability）
安定なソート：同じキーの要素の相対的な順序が保たれる。
students = [("Alice", 85), ("Bob", 92), ("Carol", 85), ("Dave", 92)]
# 安定ソート（点数で降順）:
# [("Bob", 92), ("Dave", 92), ("Alice", 85), ("Carol", 85)]
# → Bob と Dave の順序が保たれている（元の順）
# 不安定ソート:
# [("Dave", 92), ("Bob", 92), ("Carol", 85), ("Alice", 85)]
# → 順序が入れ替わる可能性がある| ソート | 安定 | 時間（平均） | 時間（最悪） | 空間 |
|---|---|---|---|---|
| MergeSort | ✅ | O(n log n) | O(n log n) | O(n) |
| QuickSort | ❌ | O(n log n) | O(n²) | O(log n) |
| HeapSort | ❌ | O(n log n) | O(n log n) | O(1) |
| Timsort | ✅ | O(n log n) | O(n log n) | O(n) |
| InsertionSort | ✅ | O(n²) | O(n²) | O(1) |
非比較ソート：O(n) を超える
値の範囲が限られている場合、比較せずにソートできる。
Counting Sort
def counting_sort(arr: list[int], max_val: int) -> list[int]:
"""値の範囲が [0, max_val] の場合 — O(n + k), k = max_val"""
count = [0] * (max_val + 1)
for x in arr:
count[x] += 1
result = []
for val, cnt in enumerate(count):
result.extend([val] * cnt)
return resultRadix Sort
def radix_sort(arr: list[int]) -> list[int]:
"""桁ごとに Counting Sort — O(d × (n + k)), d = 桁数"""
if not arr:
return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arrQuickSelect：K番目の要素を O(n) で求める
ソートの副産物。QuickSort の partition を片側だけ再帰する。
def quickselect(arr: list, k: int) -> int:
"""k 番目に小さい要素を返す（0-indexed）— 平均 O(n)"""
def select(lo, hi):
if lo == hi:
return arr[lo]
pivot_idx = partition_random(arr, lo, hi)
if k == pivot_idx:
return arr[k]
elif k < pivot_idx:
return select(lo, pivot_idx - 1)
else:
return select(pivot_idx + 1, hi)
return select(0, len(arr) - 1)まとめ
| アルゴリズム | 時間 | 空間 | 安定 | 最適な場面 |
|---|---|---|---|---|
| QuickSort | O(n log n) avg | O(log n) | ❌ | 汎用・インプレース |
| MergeSort | O(n log n) | O(n) | ✅ | 安定性が必要・連結リスト |
| HeapSort | O(n log n) | O(1) | ❌ | メモリが厳しい環境 |
| Timsort | O(n log n) | O(n) | ✅ | ほぼソート済みデータ |
| Counting | O(n + k) | O(k) | ✅ | 値の範囲が小さい整数 |
| Radix | O(d(n+k)) | O(n+k) | ✅ | 固定桁数の整数 |