ソートアルゴリズム
ソートはコンピュータサイエンス最古にして最重要の問題の一つである。比較ベースのソートには Omega(n log n) の理論的下限が存在し、この限界を理解することがアルゴリズム設計全般の深い洞察につながる。本章では、基本的なソートから高度なソートまでを網羅的に解説し、理論と実装の両面からソートの全体像を把握する。
128 分で読めます63,586 文字
ソートアルゴリズム
ソートはコンピュータサイエンス最古にして最重要の問題の一つである。比較ベースのソートには Omega(n log n) の理論的下限が存在し、この限界を理解することがアルゴリズム設計全般の深い洞察につながる。本章では、基本的なソートから高度なソートまでを網羅的に解説し、理論と実装の両面からソートの全体像を把握する。
この章で学ぶこと
- 主要なソートアルゴリズム 8 種類の仕組みと計算量を正確に説明できる
- 各ソートの安定性、空間計算量、適用場面を理解し使い分けられる
- O(n log n) 比較下限定理の証明を理解し、非比較ソートとの違いを説明できる
- Timsort, Introsort 等の実用的ハイブリッドソートの設計思想を説明できる
- 外部ソートや並列ソートなど、大規模データ処理のソート手法を概観できる
- コード上でのソートの正しい使い方とアンチパターンを判別できる
前提知識
- 再帰と分割統治法の基礎概念
- 配列・リストの基本操作
1. ソートアルゴリズムの全体像
ソートアルゴリズムは、大きく「比較ベースのソート」と「非比較ベースのソート」に分類される。比較ベースのソートは要素間の大小比較によって順序を決定し、理論的に Omega(n log n) という下限が存在する。一方、非比較ベースのソートは要素の値そのものの構造（桁、範囲など）を利用することで、特定の条件下ではこの下限を打破できる。
1.1 分類の全体図
ソートアルゴリズム
|
+------------+------------+
| |
比較ベースソート 非比較ベースソート
| |
+-------+-------+ +-------+-------+
| | | | | |
O(n^2) O(n logn) ハイブリッド 計数 基数 バケット
| | |
+--+--+ +--+--+ +--+--+
| | | | | | | | |
バブ 選択 挿入 マージ QS ヒープ Tim Intro pdq
ル ソート sort sort sort
1.2 ソートアルゴリズム総合比較表
以下の表は、本章で扱うすべてのソートアルゴリズムの計算量と特性をまとめたものである。
+================+============+============+============+=======+=======+====================+
| アルゴリズム | 最悪計算量 | 平均計算量 | 最良計算量 | 空間 | 安定 | 主な用途 |
+================+============+============+============+=======+=======+====================+
| バブルソート | O(n^2) | O(n^2) | O(n) | O(1) | Yes | 教育用 |
+----------------+------------+------------+------------+-------+-------+--------------------+
| 選択ソート | O(n^2) | O(n^2) | O(n^2) | O(1) | No | 交換回数最小化 |
+----------------+------------+------------+------------+-------+-------+--------------------+
| 挿入ソート | O(n^2) | O(n^2) | O(n) | O(1) | Yes | 小規模/ほぼ整列済 |
+----------------+------------+------------+------------+-------+-------+--------------------+
| シェルソート | O(n^1.5) | 間隔依存 | O(n log n) | O(1) | No | 中規模の汎用 |
+----------------+------------+------------+------------+-------+-------+--------------------+
| マージソート | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | 安定性必須の場面 |
+----------------+------------+------------+------------+-------+-------+--------------------+
| クイックソート | O(n^2) | O(n log n) | O(n log n) | O(logn)| No | 汎用（高速） |
+----------------+------------+------------+------------+-------+-------+--------------------+
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | O(1) | No | 最悪保証+省メモリ |
+----------------+------------+------------+------------+-------+-------+--------------------+
| 計数ソート | O(n + k) | O(n + k) | O(n + k) | O(n+k)| Yes | 整数/範囲小 |
+----------------+------------+------------+------------+-------+-------+--------------------+
| 基数ソート | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k)| Yes | 固定長整数/文字列 |
+----------------+------------+------------+------------+-------+-------+--------------------+
| バケットソート | O(n^2) | O(n + k) | O(n + k) | O(n+k)| Yes | 一様分布データ |
+----------------+------------+------------+------------+-------+-------+--------------------+
| Timsort | O(n log n) | O(n log n) | O(n) | O(n) | Yes | 実データ全般 |
+----------------+------------+------------+------------+-------+-------+--------------------+
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(logn)| No | C++ STL |
+----------------+------------+------------+------------+-------+-------+--------------------+
※ k = 値の範囲、d = 桁数
2. O(n^2) のソート ― 基本ソート群
O(n^2) のソートアルゴリズムは、データ量が大きくなると性能が急激に劣化するため、大規模データには不向きである。しかし、アルゴリズム設計の基本概念（ループ不変条件、比較と交換、最悪ケース分析）を学ぶうえで極めて重要であり、また小規模データに対してはオーバーヘッドの小ささから最速となる場合がある。
2.1 バブルソート（Bubble Sort）
バブルソートは、隣接する要素を比較・交換しながら、最大値を配列の末尾に「泡」のように浮かび上がらせるアルゴリズムである。各パスで未ソート部分の最大値が確定位置に移動する。
アルゴリズムの手順
- 配列の先頭から末尾に向かって隣接要素を比較する
- 左の要素が右の要素より大きければ交換する
- 1パスの終了時に、最大値が末尾に到達する
- 未ソート部分の範囲を1つ縮めて繰り返す
- パス中に交換が一度も発生しなければ、ソート済みと判断して終了する
ASCII 図解: バブルソートの動作
配列: [5, 3, 8, 1, 4]
=== Pass 1 ===
[5, 3, 8, 1, 4] 5 > 3 → 交換
^ ^
[3, 5, 8, 1, 4] 5 < 8 → そのまま
^ ^
[3, 5, 8, 1, 4] 8 > 1 → 交換
^ ^
[3, 5, 1, 8, 4] 8 > 4 → 交換
^ ^
[3, 5, 1, 4, 8] ← 8 が確定位置に到達
確定: [8]
=== Pass 2 ===
[3, 5, 1, 4 | 8] 3 < 5 → そのまま
^ ^
[3, 5, 1, 4 | 8] 5 > 1 → 交換
^ ^
[3, 1, 5, 4 | 8] 5 > 4 → 交換
^ ^
[3, 1, 4, 5 | 8] ← 5 が確定位置に到達
確定: [5, 8]
=== Pass 3 ===
[3, 1, 4 | 5, 8] 3 > 1 → 交換
^ ^
[1, 3, 4 | 5, 8] 3 < 4 → そのまま
^ ^
[1, 3, 4 | 5, 8] ← 4 が確定位置に到達
確定: [4, 5, 8]
=== Pass 4 ===
[1, 3 | 4, 5, 8] 1 < 3 → そのまま（交換なし）
^ ^
→ 交換が 0 回なので early exit！
結果: [1, 3, 4, 5, 8] ← ソート完了
完全な実装
def bubble_sort(arr: list) -> list:
"""
バブルソート: 隣接要素を比較・交換して最大値を末尾に浮かべる。
ループ不変条件:
i 回目のパス終了後、配列の末尾 i 個の要素はソート済みかつ
最終位置に配置されている。
Args:
arr: ソート対象のリスト（破壊的に変更される）
Returns:
ソート済みのリスト（入力と同じオブジェクト）
"""
n = len(arr)
for i in range(n):
swapped = False
# 未ソート部分を走査（末尾 i 個は確定済み）
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 交換が一度も発生しなければソート済み
if not swapped:
break
return arr
# --- 動作確認 ---
assert bubble_sort([5, 3, 8, 1, 4]) == [1, 3, 4, 5, 8]
assert bubble_sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5] # 最良: 1パスで終了
assert bubble_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5] # 最悪: 逆順
assert bubble_sort([]) == []
assert bubble_sort([42]) == [42]計算量分析
- 最悪計算量 O(n^2): 配列が逆順の場合。すべてのパスですべての比較・交換が発生する。比較回数は n(n-1)/2 回。
- 平均計算量 O(n^2): ランダムな入力に対しても、平均的に約 n^2/4 回の比較と交換が発生する。
- 最良計算量 O(n): 配列がすでにソート済みの場合。early exit により 1 パス（n-1 回の比較）で終了する。
- 空間計算量 O(1): 一時変数のみ使用するインプレースアルゴリズム。
- 安定性: Yes: 等しい要素は交換されないため、相対順序が保持される。
バブルソートの変種
カクテルシェーカーソート（双方向バブルソート）: 左から右へのパスと右から左へのパスを交互に行う変種。「亀（末尾に近い小さな値）」の問題を軽減する。
def cocktail_shaker_sort(arr: list) -> list:
"""双方向バブルソート。前方パスと後方パスを交互に実行する。"""
n = len(arr)
start = 0
end = n - 1
swapped = True
while swapped:
swapped = False
# 前方パス: 左 → 右
for i in range(start, end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
end -= 1
if not swapped:
break
swapped = False
# 後方パス: 右 → 左
for i in range(end, start, -1):
if arr[i] < arr[i - 1]:
arr[i], arr[i - 1] = arr[i - 1], arr[i]
swapped = True
start += 1
return arr
assert cocktail_shaker_sort([5, 3, 8, 1, 4]) == [1, 3, 4, 5, 8]2.2 選択ソート（Selection Sort）
選択ソートは、未ソート部分から最小値を見つけ出し、先頭の未ソート位置と交換する操作を繰り返すアルゴリズムである。交換回数が O(n) と最少であるのが特徴。
アルゴリズムの手順
- 未ソート部分から最小値を線形探索で見つける
- 最小値を未ソート部分の先頭と交換する
- ソート済み部分の範囲を1つ拡大する
- 未ソート部分がなくなるまで繰り返す
ASCII 図解: 選択ソートの動作
配列: [29, 10, 14, 37, 13]
=== Step 1: 最小値を探索 ===
[29, 10, 14, 37, 13]
^^ ← 最小値 = 10（index 1）
先頭(index 0) と交換
[10, 29, 14, 37, 13]
~~ ← 確定: [10]
=== Step 2: 残りから最小値を探索 ===
[10 | 29, 14, 37, 13]
^^ ← 最小値 = 13（index 4）
index 1 と交換
[10, 13, 14, 37, 29]
~~ ~~ ← 確定: [10, 13]
=== Step 3: 残りから最小値を探索 ===
[10, 13 | 14, 37, 29]
^^ ← 最小値 = 14（index 2、自分自身）
交換不要
[10, 13, 14, 37, 29]
~~ ~~ ~~ ← 確定: [10, 13, 14]
=== Step 4: 残りから最小値を探索 ===
[10, 13, 14 | 37, 29]
^^ ← 最小値 = 29（index 4）
index 3 と交換
[10, 13, 14, 29, 37]
~~ ~~ ~~ ~~ ~~ ← 全要素確定
結果: [10, 13, 14, 29, 37]
完全な実装
def selection_sort(arr: list) -> list:
"""
選択ソート: 未ソート部分から最小値を選び先頭に配置する。
ループ不変条件:
i 回目の反復開始時、arr[0:i] はソート済みかつ
arr[i:] のすべての要素以下である。
Args:
arr: ソート対象のリスト（破壊的に変更される）
Returns:
ソート済みのリスト
"""
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 最小値が現在位置と異なる場合のみ交換
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# --- 動作確認 ---
assert selection_sort([29, 10, 14, 37, 13]) == [10, 13, 14, 29, 37]
assert selection_sort([1, 2, 3]) == [1, 2, 3]
assert selection_sort([3, 2, 1]) == [1, 2, 3]計算量分析
- 最悪/平均/最良計算量: すべて O(n^2): 入力の状態に関係なく、常に n(n-1)/2 回の比較を行う。
- 空間計算量 O(1): インプレース。
- 安定性: No: 離れた要素を交換するため、同値要素の相対順序が崩れうる。
例: [3a, 3b, 1] をソートすると [1, 3b, 3a] となり、3a と 3b の順序が逆転する。
選択ソートが不安定になる具体例
入力: [3a, 3b, 1]
※ 3a, 3b は同じ値 3 だが、元の順序は a が先
Step 1: 最小値 = 1 (index 2)
index 0 (3a) と index 2 (1) を交換
→ [1, 3b, 3a]
^^ ← 3a と 3b の相対順序が逆転！
結果: [1, 3b, 3a] ← 不安定
選択ソートの利点と欠点
利点:
- 交換回数が最大 n-1 回。書き込みコストが高い環境（フラッシュメモリ等）で有利
- アルゴリズムが単純で実装ミスが少ない
- データの移動量が少ない
欠点:
- 入力が整列済みでも計算量が変わらない（適応性がない）
- 不安定ソートである
- 大規模データには不適
2.3 挿入ソート（Insertion Sort）
挿入ソートは、トランプのカードを手札に挿入するように、未ソート部分の先頭要素をソート済み部分の正しい位置に挿入するアルゴリズムである。ほぼソート済みのデータに対して極めて高速であり、多くのハイブリッドソートの内部で使用されている。
アルゴリズムの手順
- 配列の 2 番目の要素から開始する（1 番目の要素は単独でソート済みとみなす）
- 現在の要素（キー）を一時的に保存する
- ソート済み部分を右から左に走査し、キーより大きな要素を 1 つ右にシフトする
- 空いた位置にキーを挿入する
- 配列末尾まで繰り返す
ASCII 図解: 挿入ソートの動作
配列: [7, 3, 5, 1, 9]
ソート済み | 未ソート
-----------+---------
[7] | [3, 5, 1, 9] key = 3
3 < 7 → 7を右にシフト
[_, 7] key=3 を位置0に挿入
[3, 7] | [5, 1, 9]
[3, 7] | [5, 1, 9] key = 5
5 < 7 → 7を右にシフト
5 > 3 → 停止
[3, _, 7] key=5 を位置1に挿入
[3, 5, 7] | [1, 9]
[3, 5, 7] | [1, 9] key = 1
1 < 7 → 7を右にシフト
1 < 5 → 5を右にシフト
1 < 3 → 3を右にシフト
先頭に到達 → 停止
[_, 3, 5, 7] key=1 を位置0に挿入
[1, 3, 5, 7] | [9]
[1, 3, 5, 7] | [9] key = 9
9 > 7 → 停止（シフトなし）
[1, 3, 5, 7, 9] ← ソート完了
完全な実装
def insertion_sort(arr: list) -> list:
"""
挿入ソート: 各要素をソート済み部分の正しい位置に挿入する。
ループ不変条件:
i 回目の反復開始時、arr[0:i] は元の arr[0:i] の要素を
ソート済みの順序で含んでいる。
Args:
arr: ソート対象のリスト（破壊的に変更される）
Returns:
ソート済みのリスト
"""
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# key より大きい要素を右にシフト
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# key を正しい位置に挿入
arr[j + 1] = key
return arr
# --- 動作確認 ---
assert insertion_sort([7, 3, 5, 1, 9]) == [1, 3, 5, 7, 9]
assert insertion_sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5] # 最良: O(n)
assert insertion_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5] # 最悪: O(n^2)計算量分析
- 最悪計算量 O(n^2): 配列が逆順の場合。各要素を先頭まで移動する必要がある。比較回数とシフト回数がともに n(n-1)/2。
- 平均計算量 O(n^2): ランダムな入力に対しては平均 n^2/4 回の比較。
- 最良計算量 O(n): ソート済みの場合。各要素について 1 回の比較のみで位置が確定する。
- 空間計算量 O(1): インプレース。
- 安定性: Yes:
arr[j] > keyの比較で等しい要素は移動しないため、相対順序が保持される。
挿入ソートの重要な性質
適応性（Adaptivity）: 挿入ソートの実行時間は「転倒数（inversions）」に比例する。転倒数とは、i < j かつ arr[i] > arr[j] であるペア (i, j) の数である。ソート済み配列の転倒数は 0、逆順配列の転倒数は n(n-1)/2 である。ほぼソート済みのデータ（転倒数が O(n) のオーダー）に対しては、挿入ソートは O(n) で動作する。
オンライン性: データが逐次到着する場合でもソートを維持できる。ストリーミングデータの処理に適している。
小規模データでの優位性: ループのオーバーヘッドが小さく、キャッシュ効率が高いため、n が小さい場合（概ね n < 50 程度）には O(n log n) アルゴリズムよりも高速になることが多い。Python の Timsort や C++ の Introsort は、小さい部分配列に対して挿入ソートを使用している。
二分挿入ソート
挿入位置の探索に二分探索を用いる変種。比較回数を O(n log n) に削減できるが、シフト操作が O(n^2) のままであるため、全体の計算量は O(n^2) から改善されない。ただし、比較コストが高い場合（複雑なオブジェクトの比較など）には有効である。
import bisect
def binary_insertion_sort(arr: list) -> list:
"""二分探索で挿入位置を決定する挿入ソート。"""
for i in range(1, len(arr)):
key = arr[i]
# bisect_left で挿入位置を二分探索（O(log i)）
pos = bisect.bisect_left(arr, key, 0, i)
# pos から i-1 までの要素を右に 1 つシフト（O(i)）
for j in range(i, pos, -1):
arr[j] = arr[j - 1]
arr[pos] = key
return arr
assert binary_insertion_sort([7, 3, 5, 1, 9]) == [1, 3, 5, 7, 9]2.4 シェルソート（Shell Sort）
シェルソートは、挿入ソートを一般化したアルゴリズムである。離れた位置にある要素を先に比較・交換することで、大きな「転倒」を早期に解消し、最終的な挿入ソートの負荷を軽減する。
アルゴリズムの手順
- 間隔（ギャップ）列を決定する（例: n/2, n/4, ..., 1）
- 各ギャップに対して、ギャップ間隔の挿入ソートを実行する
- ギャップを縮小しながら繰り返す
- 最後にギャップ 1 の挿入ソート（通常の挿入ソート）を実行して完了する
完全な実装
def shell_sort(arr: list) -> list:
"""
シェルソート: ギャップ付き挿入ソートを段階的に適用する。
ギャップ列は Shell の元論文に従い n//2, n//4, ..., 1 を使用。
より良いギャップ列（Knuth, Sedgewick 等）を使うと
計算量が改善される。
Args:
arr: ソート対象のリスト（破壊的に変更される）
Returns:
ソート済みのリスト
"""
n = len(arr)
gap = n // 2
while gap > 0:
# ギャップ間隔の挿入ソート
for i in range(gap, n):
key = arr[i]
j = i
while j >= gap and arr[j - gap] > key:
arr[j] = arr[j - gap]
j -= gap
arr[j] = key
gap //= 2
return arr
# --- 動作確認 ---
assert shell_sort([12, 34, 54, 2, 3]) == [2, 3, 12, 34, 54]
assert shell_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]ギャップ列の選択と計算量
シェルソートの計算量は、選択するギャップ列に大きく依存する。
+============================+==========================+================+
| ギャップ列 | 考案者 | 最悪計算量 |
+============================+==========================+================+
| n/2, n/4, ..., 1 | Shell (1959) | O(n^2) |
+----------------------------+--------------------------+----------------+
| 2^k - 1: 1, 3, 7, 15, ... | Hibbard (1963) | O(n^(3/2)) |
+----------------------------+--------------------------+----------------+
| 3^k-1)/2: 1, 4, 13, 40,...| Knuth (1973) | O(n^(3/2)) |
+----------------------------+--------------------------+----------------+
| 素数列ベース | Sedgewick (1986) | O(n^(4/3)) |
+----------------------------+--------------------------+----------------+
| 1, 4, 10, 23, 57, 132, ...| Ciura (2001, 経験的最適) | 未証明（高速） |
+----------------------------+--------------------------+----------------+
シェルソートの計算量の正確な解析は、ギャップ列に依存する組合せ論的な難問として未解決の部分が残されている。
3. O(n log n) のソート ― 分割統治と優先度キュー
3.1 マージソート（Merge Sort）
マージソートは、分割統治法（Divide and Conquer）の代表的な応用である。配列を再帰的に半分に分割し、個々の部分配列をソートした後に統合（マージ）する。計算量が入力の状態に依存せず、常に O(n log n) であり、安定ソートである点が大きな利点。
アルゴリズムの手順
- 配列の長さが 1 以下ならそのまま返す（基底ケース）
- 配列を中央で二分割する
- 左半分と右半分をそれぞれ再帰的にソートする
- ソート済みの 2 つの部分配列をマージする
ASCII 図解: マージソートの分割と統合
[38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43, 3] [9, 82, 10]
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
/ \ / \ / \ |
[38] [27] [43] [3] [9] [82] [10]
\ / \ / \ / |
[27, 38] [3, 43] [9, 82] [10] ← マージ（各段 O(n)）
\ / \ /
[3, 27, 38, 43] [9, 10, 82]
\ /
[3, 9, 10, 27, 38, 43, 82] ← log n 段
総計算量 = O(n) x O(log n) = O(n log n)
マージ操作の詳細図解
マージ: [3, 27, 38, 43] と [9, 10, 82] を統合
左: [3, 27, 38, 43] 右: [9, 10, 82] 結果: []
^ ^
L R
Step 1: 3 < 9 → 3 を結果に追加
左: [3, 27, 38, 43] 右: [9, 10, 82] 結果: [3]
^ ^
Step 2: 27 > 9 → 9 を結果に追加
左: [3, 27, 38, 43] 右: [9, 10, 82] 結果: [3, 9]
^ ^
Step 3: 27 > 10 → 10 を結果に追加
左: [3, 27, 38, 43] 右: [9, 10, 82] 結果: [3, 9, 10]
^ ^
Step 4: 27 < 82 → 27 を結果に追加
左: [3, 27, 38, 43] 右: [9, 10, 82] 結果: [3, 9, 10, 27]
^ ^
Step 5: 38 < 82 → 38 を結果に追加
Step 6: 43 < 82 → 43 を結果に追加
左: 終了 右: [82] 残り
Step 7: 右の残り [82] をそのまま追加
結果: [3, 9, 10, 27, 38, 43, 82] ← マージ完了
完全な実装
def merge_sort(arr: list) -> list:
"""
マージソート: 分割統治法による安定ソート。
計算量:
- 最悪/平均/最良: O(n log n)
- 空間: O(n)（マージ用の一時配列）
- 安定: Yes
Args:
arr: ソート対象のリスト
Returns:
新しいソート済みリスト
"""
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:
"""ソート済みの 2 つのリストを 1 つのソート済みリストに統合する。"""
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 result
# --- 動作確認 ---
assert merge_sort([38, 27, 43, 3, 9, 82, 10]) == [3, 9, 10, 27, 38, 43, 82]
assert merge_sort([]) == []
assert merge_sort([1]) == [1]計算量の厳密な導出
マージソートの再帰関係式:
T(n) = 2 * T(n/2) + O(n) （n > 1 のとき）
T(1) = O(1)
マスター定理を適用:
a = 2, b = 2, f(n) = O(n)
n^(log_b(a)) = n^(log_2(2)) = n^1 = n
f(n) = O(n) = O(n^(log_b(a)))
→ ケース 2 に該当: T(n) = O(n log n)
再帰木で直感的に理解:
深さ 0: 1 個の問題、各サイズ n → 仕事量 n
深さ 1: 2 個の問題、各サイズ n/2 → 仕事量 n
深さ 2: 4 個の問題、各サイズ n/4 → 仕事量 n
...
深さ k: 2^k 個の問題、各サイズ n/2^k → 仕事量 n
...
深さ log n: n 個の問題、各サイズ 1 → 仕事量 n
合計 = n × (log n + 1) = O(n log n)
ボトムアップマージソート
再帰を使わないマージソートの実装。再帰のスタックオーバーフローを回避でき、定数倍が若干小さい。
def merge_sort_bottom_up(arr: list) -> list:
"""
ボトムアップ（非再帰）マージソート。
サイズ 1 の部分配列から始めて、マージするサイズを倍増させていく。
"""
n = len(arr)
if n <= 1:
return arr[:]
# 作業用コピー
result = arr[:]
width = 1
while width < n:
for start in range(0, n, 2 * width):
mid = min(start + width, n)
end = min(start + 2 * width, n)
left = result[start:mid]
right = result[mid:end]
merged = _merge(left, right)
result[start:start + len(merged)] = merged
width *= 2
return result
assert merge_sort_bottom_up([38, 27, 43, 3, 9, 82, 10]) == [3, 9, 10, 27, 38, 43, 82]3.2 クイックソート（Quick Sort）
クイックソートは、C.A.R. Hoare が 1960 年に考案したアルゴリズムで、分割統治法に基づく。ピボット要素を選択し、配列をピボット以下とピボット以上の 2 つの部分に分割（パーティション）した後、それぞれを再帰的にソートする。平均計算量は O(n log n) であり、定数倍の小ささとキャッシュ効率の良さから、多くの実装で最も高速なソートとして採用されている。
アルゴリズムの手順
- ピボット要素を選択する（選択戦略は複数ある）
- 配列をパーティションする: ピボット以下の要素を左側、ピボット以上の要素を右側に移動する
- 左側部分配列と右側部分配列をそれぞれ再帰的にソートする
ASCII 図解: クイックソートのパーティション操作（Lomuto 方式）
配列: [8, 3, 5, 1, 4, 2, 7, 6] ピボット = arr[high] = 6
初期状態:
i = -1 (ピボット以下の領域の右端)
j = 0 (走査位置)
[8, 3, 5, 1, 4, 2, 7, 6]
j pivot
i=-1
j=0: arr[0]=8 > 6 → 何もしない
[8, 3, 5, 1, 4, 2, 7, 6]
j
j=1: arr[1]=3 <= 6 → i++, swap(arr[1], arr[1]) ※ i=0
[3, 8, 5, 1, 4, 2, 7, 6] ← 3 と 8 を交換
i j
j=2: arr[2]=5 <= 6 → i++, swap(arr[2], arr[2]) ※ i=1
[3, 5, 8, 1, 4, 2, 7, 6] ← 5 と 8 を交換
i j
j=3: arr[3]=1 <= 6 → i++, swap(arr[3], arr[3]) ※ i=2
[3, 5, 1, 8, 4, 2, 7, 6] ← 1 と 8 を交換
i j
j=4: arr[4]=4 <= 6 → i++, swap(arr[3], arr[4]) ※ i=3
[3, 5, 1, 4, 8, 2, 7, 6] ← 4 と 8 を交換
i j
j=5: arr[5]=2 <= 6 → i++, swap(arr[4], arr[5]) ※ i=4
[3, 5, 1, 4, 2, 8, 7, 6] ← 2 と 8 を交換
i j
j=6: arr[6]=7 > 6 → 何もしない
[3, 5, 1, 4, 2, 8, 7, 6]
i j
最後: swap(arr[i+1], arr[high]) ※ pivot を正しい位置に
[3, 5, 1, 4, 2, 6, 7, 8]
^
ピボット確定位置 (index 5)
結果:
[3, 5, 1, 4, 2] 6 [7, 8]
ピボット以下 pivot ピボット以上
→ 再帰的にソート → 再帰的にソート
完全な実装（教育用リスト内包表記版）
def quicksort_simple(arr: list) -> list:
"""
クイックソート: 簡潔なリスト内包表記版（教育用）。
注意: この実装は O(n) の追加メモリを使用する。
インプレース版は後述。
Args:
arr: ソート対象のリスト
Returns:
新しいソート済みリスト
"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort_simple(left) + middle + quicksort_simple(right)
assert quicksort_simple([8, 3, 5, 1, 4, 2, 7, 6]) == [1, 2, 3, 4, 5, 6, 7, 8]完全な実装（インプレース版 + ピボット戦略）
import random
def quicksort_inplace(arr: list, low: int = 0, high: int = None) -> list:
"""
クイックソート: インプレース版。
ランダムピボット選択で最悪ケースを確率的に回避する。
計算量:
- 最悪: O(n^2) — ピボットが常に最大/最小
- 平均: O(n log n) — ランダムピボットの期待値
- 空間: O(log n) — 再帰の深さ（インプレース）
- 安定: No
Args:
arr: ソート対象のリスト（破壊的に変更される）
low: ソート範囲の開始インデックス
high: ソート範囲の終了インデックス
Returns:
ソート済みのリスト（入力と同じオブジェクト）
"""
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = _partition_random(arr, low, high)
quicksort_inplace(arr, low, pivot_idx - 1)
quicksort_inplace(arr, pivot_idx + 1, high)
return arr
def _partition_random(arr: list, low: int, high: int) -> int:
"""ランダムピボット選択 + Lomuto パーティション。"""
# ランダムな要素をピボットに選び、末尾に移動
rand_idx = random.randint(low, high)
arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# --- 動作確認 ---
test = [8, 3, 5, 1, 4, 2, 7, 6]
quicksort_inplace(test)
assert test == [1, 2, 3, 4, 5, 6, 7, 8]ピボット選択戦略の比較
ピボットの選択はクイックソートの性能に決定的な影響を与える。
+==========================+===================+============================+
| 戦略 | 最悪ケース | 特徴 |
+==========================+===================+============================+
| 先頭/末尾の要素 | ソート済み配列で | 最も単純だが危険 |
| | O(n^2) に退化 | |
+--------------------------+-------------------+----------------------------+
| ランダム選択 | 確率的に回避 | 期待計算量 O(n log n) |
| | | 最悪ケースは理論上残る |
+--------------------------+-------------------+----------------------------+
| 三数の中央値 | 大幅に改善 | low, mid, high の中央値 |
| (Median-of-Three) | | 多くの実装で採用 |
+--------------------------+-------------------+----------------------------+
| 九数の中央値 | さらに改善 | 3 グループの中央値の中央値 |
| (Ninther) | | 大規模データ向け |
+--------------------------+-------------------+----------------------------+
| 中央値の中央値 | O(n log n) 保証 | 理論的に最適だが |
| (Median of Medians) | （最悪でも） | 定数倍が大きく非実用的 |
+--------------------------+-------------------+----------------------------+
クイックソートが実務で最速な理由
- キャッシュ局所性: 配列の連続領域に対して順次アクセスするため、CPU キャッシュのヒット率が高い
- 定数倍の小ささ: 比較・交換の操作が単純で、各反復のオーバーヘッドが小さい
- インプレース動作: 追加メモリの割り当て・解放が不要
- 分岐予測の効率: パーティション操作中の条件分岐が予測しやすい
- 末尾再帰の最適化: 短い方の部分配列を先に処理し、長い方を末尾再帰にすることで、スタック使用量を O(log n) に抑えられる
3.3 ヒープソート（Heap Sort）
ヒープソートは、最大ヒープ（Max-Heap）のデータ構造を利用したソートアルゴリズムである。最悪計算量が O(n log n) で保証され、かつインプレースで動作するのが特徴。ただし、キャッシュ効率の悪さから、実務ではクイックソートに性能面で劣ることが多い。
ヒープの基本構造
最大ヒープ: 親 >= 子 であるような完全二分木
配列 [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] のヒープ表現:
16 ← index 0
/ \
14 10 ← index 1, 2
/ \ / \
8 7 9 3 ← index 3, 4, 5, 6
/ \ |
2 4 1 ← index 7, 8, 9
親の index: i → 子: 2i+1 (左), 2i+2 (右)
子の index: i → 親: (i-1)//2
アルゴリズムの手順
- 配列を最大ヒープに変換する（Build-Max-Heap）
- ヒープの先頭（最大値）を末尾と交換する
- ヒープサイズを 1 縮小し、ヒープ性を回復する（Heapify）
- ヒープサイズが 1 になるまで 2-3 を繰り返す
ASCII 図解: ヒープソートの動作
初期配列: [4, 10, 3, 5, 1]
=== Phase 1: Build Max-Heap ===
ボトムアップに heapify を適用
index 1 (値10) を heapify: すでにヒープ性あり
index 0 (値4) を heapify:
4 < 10 → 交換 → 10 が根に
4 < 5 → 交換 → 5 が左子に
最大ヒープ完成:
10
/ \
5 3
/ \
4 1
配列: [10, 5, 3, 4, 1]
=== Phase 2: ソート ===
Step 1: arr[0]=10 と arr[4]=1 を交換 → [1, 5, 3, 4, |10]
heapify(0, size=4):
1 5
/ \ → / \
5 3 4 3
/ /
4 1
配列: [5, 4, 3, 1, |10]
Step 2: arr[0]=5 と arr[3]=1 を交換 → [1, 4, 3, |5, 10]
heapify(0, size=3):
1 → 4
/ \ / \
4 3 1 3
配列: [4, 1, 3, |5, 10]
Step 3: arr[0]=4 と arr[2]=3 を交換 → [3, 1, |4, 5, 10]
heapify(0, size=2):
3 → 3
/ /
1 1
配列: [3, 1, |4, 5, 10]
Step 4: arr[0]=3 と arr[1]=1 を交換 → [1, |3, 4, 5, 10]
配列: [1, 3, 4, 5, 10] ← ソート完了！
完全な実装
def heapsort(arr: list) -> list:
"""
ヒープソート: 最大ヒープを利用したインプレースソート。
計算量:
- 最悪/平均/最良: O(n log n)
- 空間: O(1) — インプレース
- 安定: No
Args:
arr: ソート対象のリスト（破壊的に変更される）
Returns:
ソート済みのリスト
"""
n = len(arr)
# Phase 1: Build Max-Heap（ボトムアップ）
# 最後の非葉ノード (n//2 - 1) から根 (0) まで heapify
for i in range(n // 2 - 1, -1, -1):
_heapify(arr, n, i)
# Phase 2: ヒープから最大値を取り出してソート
for i in range(n - 1, 0, -1):
# 最大値（根）を末尾と交換
arr[0], arr[i] = arr[i], arr[0]
# ヒープサイズを縮小して heapify
_heapify(arr, i, 0)
return arr
def _heapify(arr: list, heap_size: int, root: int) -> None:
"""
指定されたノードを根とする部分木のヒープ性を回復する。
Args:
arr: ヒープを表す配列
heap_size: ヒープとして扱う要素数
root: ヒープ性を回復する部分木の根のインデックス
"""
largest = root
left = 2 * root + 1
right = 2 * root + 2
if left < heap_size and arr[left] > arr[largest]:
largest = left
if right < heap_size and arr[right] > arr[largest]:
largest = right
if largest != root:
arr[root], arr[largest] = arr[largest], arr[root]
# 交換先の部分木で再帰的にヒープ性を回復
_heapify(arr, heap_size, largest)
# --- 動作確認 ---
assert heapsort([4, 10, 3, 5, 1]) == [1, 3, 4, 5, 10]
assert heapsort([1]) == [1]
assert heapsort([]) == []
assert heapsort([5, 5, 5]) == [5, 5, 5]Build-Max-Heap の計算量が O(n) である理由
直感的には、n/2 個のノードに対して O(log n) の heapify を適用するため O(n log n) に思えるが、実際には O(n) である。
深さ d のノード数: n / 2^(d+1)
深さ d のノードの heapify コスト: O(d)
合計 = sum_{d=0}^{log n} (n / 2^(d+1)) * d
= (n/2) * sum_{d=0}^{log n} d / 2^d
≤ (n/2) * sum_{d=0}^{inf} d / 2^d
= (n/2) * 2
= n
= O(n)
※ 級数 sum_{d=0}^{inf} d * x^d = x / (1-x)^2 で x = 1/2 を代入すると 2
葉ノード（全体の約半数）は heapify 不要であり、深いノードほど少ない heapify で済むため、全体として線形時間に収まる。
ヒープソートの位置づけ
| 特性 | クイックソート | マージソート | ヒープソート |
|---|---|---|---|
| 最悪計算量 | O(n^2) | O(n log n) | O(n log n) |
| 空間計算量 | O(log n) | O(n) | O(1) |
| 安定性 | No | Yes | No |
| キャッシュ効率 | 高い | 中程度 | 低い |
ヒープソートは「最悪 O(n log n) 保証」と「O(1) 空間」を同時に満たす唯一のアルゴリズムである。メモリ制約が厳しい環境や、最悪計算量の保証が必要な場面（リアルタイムシステム等）で価値がある。
4. 非比較ベースのソート
比較ベースのソートには Omega(n log n) の理論的下限があるが、非比較ベースのソートは要素の「値」そのものの構造を利用することで、この下限を打破できる。ただし、適用可能なデータ型や範囲に制約がある。
4.1 比較下限定理
比較ベースのソートの理論的下限を厳密に証明する。
決定木モデル
比較ベースのソートアルゴリズムの動作は「決定木」として表現できる。各内部ノードは 1 回の比較（a_i <= a_j ?）を表し、左の子は Yes、右の子は No の場合に進む分岐を表す。葉ノードはソートの結果（順列）を表す。
n = 3 の場合の決定木の例:
a1 <= a2 ?
/ \
Yes No
/ \
a2 <= a3 ? a1 <= a3 ?
/ \ / \
Yes No Yes No
/ \ / \
a1,a2,a3 a1 <= a3 ? a2,a1,a3 a2 <= a3 ?
/ \ / \
Yes No Yes No
/ \ / \
a1,a3,a2 a3,a1,a2 a2,a3,a1 a3,a2,a1
葉の数 = 3! = 6（すべての順列）
木の高さ = 3（最悪の比較回数）
定理と証明
定理: 比較ベースのソートアルゴリズムの最悪比較回数は Omega(n log n) である。
証明:
n 個の要素のソートには n! 通りの出力がありうる。
決定木の葉の数 L は L >= n! でなければならない。
高さ h の二分木の葉の数の上限は 2^h であるから:
2^h >= n!
h >= log_2(n!)
スターリングの近似 n! ~ sqrt(2*pi*n) * (n/e)^n より:
log_2(n!) = log_2(sqrt(2*pi*n)) + n * log_2(n/e)
= Theta(n log n)
したがって:
h >= Omega(n log n)
決定木の高さ = 最悪の比較回数であるから、
比較ベースのソートの最悪計算量は Omega(n log n) である。 Q.E.D.
より精密な下限: log_2(n!) = n*log_2(n) - n*log_2(e) + O(log n)
~ n*log_2(n) - 1.443*n
この定理は、マージソートやヒープソートが比較ベースのソートとして漸近的に最適であることを意味する。
4.2 計数ソート（Counting Sort）
計数ソートは、各値の出現回数を数え上げ、その情報を用いて要素を正しい位置に配置するアルゴリズムである。値の範囲 k が n に対して小さい場合に O(n + k) で動作する。
完全な実装（安定版）
def counting_sort(arr: list, max_val: int = None) -> list:
"""
計数ソート（安定版）: 値の出現回数を数えて正しい位置に配置する。
計算量:
- 最悪/平均/最良: O(n + k) （k = max_val + 1 = 値の範囲）
- 空間: O(n + k)
- 安定: Yes
Args:
arr: 非負整数のリスト
max_val: 値の最大値（省略時は自動検出）
Returns:
新しいソート済みリスト
"""
if not arr:
return []
if max_val is None:
max_val = max(arr)
# Step 1: 各値の出現回数を数える
count = [0] * (max_val + 1)
for x in arr:
count[x] += 1
# Step 2: 累積和を計算（各値の最終位置を決定）
for i in range(1, len(count)):
count[i] += count[i - 1]
# Step 3: 後ろから走査して安定性を保証しつつ配置
output = [0] * len(arr)
for x in reversed(arr):
count[x] -= 1
output[count[x]] = x
return output
# --- 動作確認 ---
assert counting_sort([4, 2, 2, 8, 3, 3, 1]) == [1, 2, 2, 3, 3, 4, 8]
assert counting_sort([]) == []
assert counting_sort([5]) == [5]
assert counting_sort([1, 1, 1]) == [1, 1, 1]計数ソートの制約
- 非負整数のみ: 値をインデックスとして使用するため、負の値や浮動小数点数には直接適用できない（オフセットを加える等の工夫が必要）
- 値の範囲 k が大きいと非効率: k >> n の場合、空間・時間ともに無駄が多い。例えば値の範囲が 0 ~ 10^9 で要素数が 100 の場合、計数ソートは非現実的
- 汎用性の欠如: 比較関数をカスタマイズできないため、複雑なソート基準には対応できない
4.3 基数ソート（Radix Sort）
基数ソートは、数値を桁ごとに分解し、各桁に対して安定ソート（通常は計数ソート）を繰り返し適用するアルゴリズムである。d 桁の数値を O(d(n + k)) でソートできる（k は基数、通常 10 または 256）。
LSD（Least Significant Digit）基数ソート
最下位桁から最上位桁に向かって安定ソートを適用する方式。
def radix_sort_lsd(arr: list) -> list:
"""
LSD 基数ソート: 最下位桁から安定ソートを繰り返し適用する。
計算量:
- O(d * (n + k)) （d = 最大桁数, k = 基数）
- 基数 10 の場合: k = 10, d = log_10(max_val)
- 空間: O(n + k)
- 安定: Yes
Args:
arr: 非負整数のリスト
Returns:
新しいソート済みリスト
"""
if not arr:
return []
max_val = max(arr)
result = arr[:]
exp = 1 # 現在処理中の桁の位（1, 10, 100, ...）
while max_val // exp > 0:
result = _counting_sort_by_digit(result, exp)
exp *= 10
return result
def _counting_sort_by_digit(arr: list, exp: int) -> list:
"""特定の桁（exp の位）に基づく安定な計数ソート。"""
n = len(arr)
output = [0] * n
count = [0] * 10 # 基数 10
# 該当桁の値を数える
for x in arr:
digit = (x // exp) % 10
count[digit] += 1
# 累積和
for i in range(1, 10):
count[i] += count[i - 1]
# 後ろから走査（安定性保証）
for x in reversed(arr):
digit = (x // exp) % 10
count[digit] -= 1
output[count[digit]] = x
return output
# --- 動作確認 ---
assert radix_sort_lsd([170, 45, 75, 90, 802, 24, 2, 66]) == [2, 24, 45, 66, 75, 90, 170, 802]
assert radix_sort_lsd([]) == []
assert radix_sort_lsd([1]) == [1]LSD 基数ソートの動作例
入力: [170, 45, 75, 90, 802, 24, 2, 66]
=== 1の位でソート (exp=1) ===
170 → 0, 45 → 5, 75 → 5, 90 → 0
802 → 2, 24 → 4, 2 → 2, 66 → 6
結果: [170, 90, 802, 2, 24, 45, 75, 66]
=== 10の位でソート (exp=10) ===
170 → 7, 90 → 9, 802 → 0, 2 → 0
24 → 2, 45 → 4, 75 → 7, 66 → 6
結果: [802, 2, 24, 45, 66, 170, 75, 90]
=== 100の位でソート (exp=100) ===
802 → 8, 2 → 0, 24 → 0, 45 → 0
66 → 0, 170 → 1, 75 → 0, 90 → 0
結果: [2, 24, 45, 66, 75, 90, 170, 802]
ソート完了！
4.4 バケットソート（Bucket Sort）
バケットソートは、値の範囲を均等な区間（バケット）に分割し、各要素を対応するバケットに振り分けた後、各バケットを個別にソートして連結するアルゴリズムである。データが一様分布に近い場合、各バケットの要素数がほぼ均等になり、O(n) の期待計算量で動作する。
def bucket_sort(arr: list, num_buckets: int = 10) -> list:
"""
バケットソート: [0, 1) の範囲の浮動小数点数をソートする。
計算量:
- 平均: O(n + k)（一様分布の場合）
- 最悪: O(n^2)（すべてが同一バケットに集中）
- 空間: O(n + k)
- 安定: Yes（各バケットの内部ソートが安定の場合）
Args:
arr: [0, 1) の範囲の浮動小数点数のリスト
num_buckets: バケットの数
Returns:
新しいソート済みリスト
"""
if not arr:
return []
# バケットの初期化
buckets = [[] for _ in range(num_buckets)]
# 各要素を対応するバケットに振り分け
for x in arr:
bucket_idx = int(x * num_buckets)
# 境界値（x == 1.0 の場合）の処理
if bucket_idx == num_buckets:
bucket_idx -= 1
buckets[bucket_idx].append(x)
# 各バケットを個別にソート（挿入ソートが適切）
for bucket in buckets:
bucket.sort() # Python の Timsort を利用
# すべてのバケットを連結
result = []
for bucket in buckets:
result.extend(bucket)
return result
# --- 動作確認 ---
import random
test_data = [random.random() for _ in range(20)]
assert bucket_sort(test_data) == sorted(test_data)5. ハイブリッドソートと実用的ソートアルゴリズム
現代のプログラミング言語の標準ライブラリで使用されているソートアルゴリズムは、単一のアルゴリズムではなく、複数のアルゴリズムの長所を組み合わせた「ハイブリッドソート」である。
5.1 Timsort
Timsort は Tim Peters が 2002 年に Python の標準ソートとして設計したアルゴリズムで、マージソートと挿入ソートを組み合わせたハイブリッドソートである。現在では Python, Java (オブジェクト型), JavaScript (V8), Rust (stable sort) など多くの言語で採用されている。
設計思想
実世界のデータには「すでにソートされた部分列」が頻繁に含まれるという観察に基づく。Timsort はこの「自然な整列（natural run）」を検出・活用する。
アルゴリズムの概要
- Run の検出: 配列を走査し、昇順または（厳密な）降順の連続部分列（run）を見つける。降順の run は反転して昇順にする
- 最小 run 長の保証: run が短すぎる場合（minrun 未満）、挿入ソートで周辺要素を取り込んで拡張する。minrun は通常 32 ~ 64 の範囲で、配列サイズに基づいて決定される
- マージ戦略: run をスタックに積み、特定の条件（マージポリシー）に従って隣接する run をマージする。マージポリシーはマージのバランスを保ち、効率的なマージ順序を保証する
- Galloping モード: マージ中、一方の run から連続して要素が選ばれる場合、二分探索ベースの「galloping」に切り替えて高速化する
Timsort の性能特性
+============+================+====================================+
| ケース | 計算量 | 条件 |
+============+================+====================================+
| 最良 | O(n) | すでにソート済み（1 つの run） |
+------------+----------------+------------------------------------+
| 平均 | O(n log n) | ランダムなデータ |
+------------+----------------+------------------------------------+
| 最悪 | O(n log n) | 常に保証される |
+------------+----------------+------------------------------------+
| 空間 | O(n) | マージ用の一時領域 |
+------------+----------------+------------------------------------+
| 安定性 | Yes | マージソートベースのため |
+============+================+====================================+
5.2 Introsort（内省ソート）
Introsort は David Musser が 1997 年に提案したアルゴリズムで、C++ STL の std::sort で使用されている。クイックソートをベースに、再帰が深くなりすぎた場合にヒープソートに切り替え、小さい部分配列には挿入ソートを使用するハイブリッドソートである。
アルゴリズムの概要
function introsort(arr, maxdepth):
n = length(arr)
if n <= 16:
insertion_sort(arr) ← 小規模は挿入ソート
elif maxdepth == 0:
heapsort(arr) ← 深すぎたらヒープソートに退避
else:
pivot = partition(arr)
introsort(arr[..pivot], maxdepth - 1)
introsort(arr[pivot+1..], maxdepth - 1)
# 初期 maxdepth = 2 * floor(log2(n))
性能特性
- 最悪計算量: O(n log n) — ヒープソートへの切り替えにより保証
- 平均計算量: O(n log n) — クイックソートの高速性を維持
- 空間計算量: O(log n) — 再帰スタック
- 安定性: No
5.3 pdqsort（Pattern-Defeating Quicksort）
pdqsort は Orson Peters が 2021 年に発表したアルゴリズムで、Rust の sort_unstable() や Go 1.19 以降の標準ソートで採用されている。Introsort の改良版であり、データのパターンを検出して最適な戦略に自動的に切り替える。
特徴
- ソート済みデータ: O(n)（パターン検出により）
- すべて同じ値: O(n)（パーティションが即座に完了）
- ランダムデータ: クイックソート同等の性能
- 最悪ケース: ヒープソートへの退避で O(n log n) 保証
- 不安定ソート
5.4 各言語の組み込みソート比較表
+==============+===========================+=============================+
| 言語/環境 | アルゴリズム | 備考 |
+==============+===========================+=============================+
| Python | Timsort | list.sort(), sorted() |
+--------------+---------------------------+-----------------------------+
| Java | Timsort | Arrays.sort() オブジェクト型|
+--------------+---------------------------+-----------------------------+
| Java | Dual-Pivot Quicksort | Arrays.sort() プリミティブ型|
+--------------+---------------------------+-----------------------------+
| JavaScript | Timsort (V8) | Array.prototype.sort() |
+--------------+---------------------------+-----------------------------+
| C++ (GCC) | Introsort | std::sort() |
+--------------+---------------------------+-----------------------------+
| C++ (GCC) | Timsort 系 | std::stable_sort() |
+--------------+---------------------------+-----------------------------+
| Rust | Timsort 系 (merge sort) | slice::sort() 安定 |
+--------------+---------------------------+-----------------------------+
| Rust | pdqsort | slice::sort_unstable() 不安定|
+--------------+---------------------------+-----------------------------+
| Go (1.19+) | pdqsort | sort.Slice() |
+--------------+---------------------------+-----------------------------+
| Swift | Timsort 系 | Array.sorted() |
+--------------+---------------------------+-----------------------------+
6. ソートの安定性
6.1 安定性とは何か
安定なソートとは、同じキーを持つ要素の相対的な順序がソート後も保持されるソートアルゴリズムである。これは複数のキーによるソートや、段階的なソートを行う際に極めて重要な性質となる。
安定性の具体例
# --- 安定性の重要性を示す例 ---
students = [
{"name": "Alice", "score": 85, "class": "A"},
{"name": "Bob", "score": 92, "class": "B"},
{"name": "Charlie", "score": 85, "class": "A"},
{"name": "Diana", "score": 92, "class": "B"},
{"name": "Eve", "score": 78, "class": "A"},
]
# 安定ソートで点数順にソート:
# Eve(78), Alice(85), Charlie(85), Bob(92), Diana(92)
# → 同じ 85 点の Alice と Charlie は元の順序を保持
# → 同じ 92 点の Bob と Diana も元の順序を保持
# 不安定ソートの場合:
# Eve(78), Charlie(85), Alice(85), Diana(92), Bob(92)
# → 同じ点数の中での順序が保証されない6.2 多重キーソートへの応用
安定ソートの最も実用的な応用は、多重キーソートである。安定ソートを使えば、副キーでソートした後に主キーでソートするだけで、正しい多重キーソートが実現できる。
# 多重キーソート: まず副キーで、次に主キーでソートする
records = [
("Engineering", "Bob"),
("Sales", "Alice"),
("Engineering", "Alice"),
("Sales", "Charlie"),
("Engineering", "Charlie"),
]
# Step 1: 名前（副キー）で安定ソート
step1 = sorted(records, key=lambda x: x[1])
# [('Sales', 'Alice'), ('Engineering', 'Alice'),
# ('Engineering', 'Bob'),
# ('Sales', 'Charlie'), ('Engineering', 'Charlie')]
# Step 2: 部門（主キー）で安定ソート
step2 = sorted(step1, key=lambda x: x[0])
# [('Engineering', 'Alice'), ('Engineering', 'Bob'),
# ('Engineering', 'Charlie'),
# ('Sales', 'Alice'), ('Sales', 'Charlie')]
# → 部門ごとに名前順にソートされている！
# これは安定ソートだからこそ成立する。
# Python ではタプルのキーで一発で書ける:
result = sorted(records, key=lambda x: (x[0], x[1]))
assert result == step26.3 安定ソートと不安定ソートの分類
安定ソート:
- バブルソート
- 挿入ソート
- マージソート
- 計数ソート
- 基数ソート
- バケットソート（内部ソートが安定の場合）
- Timsort
不安定ソート:
- 選択ソート
- クイックソート
- ヒープソート
- シェルソート
- Introsort
- pdqsort
7. 特殊なソートと応用
7.1 外部ソート（External Sort）
メインメモリに収まりきらない大規模データをソートする手法。ディスク上のデータをチャンク単位で読み込み、ソートし、マージする。
多方向マージソートの手順
Phase 1: ソート済み run の生成| ディスク上の巨大ファイル |
|---|
| [.... 100GB のデータ ....] |
↓ メモリに収まるチャンクずつ読み込み
チャンク1 (1GB) → メモリ内ソート → ソート済みrun1 をディスクに書き出し
チャンク2 (1GB) → メモリ内ソート → ソート済みrun2 をディスクに書き出し
...
チャンク100 (1GB) → メモリ内ソート → ソート済みrun100 をディスクに書き出し
Phase 2: 多方向マージ
run1 ─┐
run2 ─┤
run3 ─┼─→ k 方向マージ → 最終ソート済みファイル
... ─┤
run100 ─┘
k 方向マージでは最小ヒープを使用:
- 各 run の先頭要素をヒープに入れる
- ヒープから最小値を取り出して出力に書き出す
- 取り出した要素の run から次の要素をヒープに追加
- すべての run が空になるまで繰り返す
I/O 計算量: O((N/B) * log_{M/B}(N/B))
N = データサイズ, B = ブロックサイズ, M = メモリサイズ7.2 並列ソート
複数のプロセッサやコアを活用してソートを高速化する手法。
並列マージソート: 分割後の各部分配列を独立したスレッド/プロセスでソートし、結果をマージする。マージ操作自体も並列化可能。
ビトニックソート（Bitonic Sort）: 並列計算に特化したソートネットワーク。比較・交換のパターンがデータに依存しないため、GPU 等の SIMD アーキテクチャに適している。O(n log^2 n) の計算量。
サンプルソート: 大規模並列環境（分散システム）向け。データからサンプルを抽出してピボットを決定し、各プロセッサにデータを分配する。MapReduce のソートフレームワークはこの原理に基づく。
7.3 部分ソートと選択アルゴリズム
配列全体をソートする必要がなく、k 番目に小さい要素だけが必要な場合、選択アルゴリズムを使用する。
def quickselect(arr: list, k: int) -> int:
"""
QuickSelect: k 番目に小さい要素を O(n) 期待時間で見つける。
（クイックソートのパーティション操作を片側だけに適用）
計算量:
- 平均: O(n)
- 最悪: O(n^2)（ランダムピボットで確率的に回避）
Args:
arr: 探索対象のリスト
k: 求める順位（0-indexed）
Returns:
k 番目に小さい要素
"""
if len(arr) == 1:
return arr[0]
pivot = arr[random.randint(0, len(arr) - 1)]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
if k < len(left):
return quickselect(left, k)
elif k < len(left) + len(middle):
return pivot
else:
return quickselect(right, k - len(left) - len(middle))
# --- 動作確認 ---
assert quickselect([3, 1, 4, 1, 5, 9, 2, 6], 0) == 1 # 最小値
assert quickselect([3, 1, 4, 1, 5, 9, 2, 6], 3) == 3 # 4番目に小さい8. アンチパターンと落とし穴
8.1 アンチパターン 1: 不適切なソートアルゴリズムの選択
問題: データの特性を考慮せずにソートアルゴリズムを選択すること。
# NG: 100万件のデータにバブルソートを使用
def process_large_dataset(data):
# バブルソートは O(n^2) → 100万件で約 10^12 回の操作
# 数時間かかる可能性がある
bubble_sort(data) # 絶対にやってはいけない
# OK: 組み込みのソートを使用
def process_large_dataset(data):
data.sort() # Timsort: O(n log n) → 100万件で約 2 x 10^7 回
# ミリ秒単位で完了
# NG: 値の範囲が 0-255 の整数データに比較ソートを使用
def sort_byte_values(data):
return sorted(data) # O(n log n)
# OK: 計数ソートを使用
def sort_byte_values(data):
return counting_sort(data, max_val=255) # O(n) で完了
# NG: ほぼソート済みのデータにクイックソートを使用
def sort_nearly_sorted(data):
quicksort_inplace(data, 0, len(data) - 1)
# ピボット選択によっては O(n^2) に退化する可能性
# OK: 挿入ソートを使用（ほぼソート済みなら O(n)）
def sort_nearly_sorted(data):
insertion_sort(data) # 転倒数が少ないため高速指針: 大規模データには言語組み込みのソートを使用するのが最も安全。特殊な条件（整数のみ、範囲が限定、ほぼソート済み等）がある場合のみ、専用アルゴリズムの採用を検討する。
8.2 アンチパターン 2: 比較関数の不整合
問題: ソートの比較関数が全順序の条件（反射性、推移性、反対称性）を満たさないこと。
# NG: 推移性を満たさない比較関数
import functools
# 「じゃんけん」のような循環的な比較
def bad_compare(a, b):
if a == "rock" and b == "scissors":
return -1
if a == "scissors" and b == "paper":
return -1
if a == "paper" and b == "rock":
return -1
return 1
# これを sorted() の key に使うと未定義動作になる
# sorted(items, key=functools.cmp_to_key(bad_compare))
# → 結果が実行ごとに異なる可能性、無限ループの危険
# NG: 浮動小数点の NaN を含むデータのソート
import math
data_with_nan = [3.0, float('nan'), 1.0, 2.0]
# sorted(data_with_nan) の結果は未定義
# NaN は任意の比較で False を返すため、全順序が成立しない
# OK: NaN を事前に除去またはキー関数で処理
def safe_sort_with_nan(data):
# NaN を無限大として扱う
return sorted(data, key=lambda x: (math.isnan(x), x if not math.isnan(x) else 0))指針: 比較関数は必ず全順序の三条件を満たすように設計する。特に浮動小数点数の NaN や、循環的な優先関係には注意が必要。
8.3 アンチパターン 3: 不要なソートの実行
問題: ソートが不要な場面でソートを使用すること。
# NG: 最小値を求めるためにソート
def find_minimum(data):
return sorted(data)[0] # O(n log n) + O(n) 空間
# OK: min() を使用
def find_minimum(data):
return min(data) # O(n)
# NG: k 番目の要素を求めるためにソート
def find_kth_smallest(data, k):
return sorted(data)[k] # O(n log n)
# OK: QuickSelect または heapq.nsmallest を使用
import heapq
def find_kth_smallest(data, k):
return heapq.nsmallest(k + 1, data)[-1] # O(n log k)
# NG: 重複除去のためにソートしてから隣接比較
def remove_duplicates(data):
data.sort()
return [data[i] for i in range(len(data)) if i == 0 or data[i] != data[i-1]]
# OK: set を使用（順序不要の場合）
def remove_duplicates(data):
return list(set(data)) # O(n) 期待時間
# OK: 順序保持が必要な場合は dict.fromkeys
def remove_duplicates_ordered(data):
return list(dict.fromkeys(data)) # O(n) 期待時間9. 実践演習
演習 Level 1: 基礎（実装と理解）
問題 1-1: マージソートの実装
マージソートをゼロから実装し、以下の 3 種類の入力に対する動作を確認せよ。
- ランダム配列（1000 要素）
- ソート済み配列（1000 要素）
- 逆順配列（1000 要素）
# テストコード
import random
import time
def test_merge_sort():
sizes = [100, 1000, 5000]
for n in sizes:
# ランダム配列
random_arr = [random.randint(0, 10000) for _ in range(n)]
assert merge_sort(random_arr) == sorted(random_arr)
# ソート済み配列
sorted_arr = list(range(n))
assert merge_sort(sorted_arr) == sorted_arr
# 逆順配列
reverse_arr = list(range(n, 0, -1))
assert merge_sort(reverse_arr) == sorted(reverse_arr)
print("All merge sort tests passed!")
test_merge_sort()問題 1-2: ソートの安定性の検証
以下のソートアルゴリズムについて、安定性を検証するテストを実装せよ。
- 挿入ソート（安定であることを確認）
- 選択ソート（不安定であることを示す反例を見つける）
# ヒント: 同じキーを持つ要素にタグを付けて、ソート後の順序を確認する
def test_stability():
data = [(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd'), (1, 'e')]
# キーの第1要素でソートし、同じキーの要素の第2要素の順序を確認する
pass # 実装せよ演習 Level 2: 応用（設計判断と最適化）
問題 2-1: ソートアルゴリズムの使い分け
以下の各状況に最適なソートアルゴリズムを選択し、その理由を述べよ。
- 100 万件のログをタイムスタンプ順にソート（安定性が必要）
- ほぼソート済みの 1000 件のセンサーデータ
- 0-255 の値を持つ 1 億件のピクセルデータ
- メモリが極端に制限された組み込みシステムでの 10 万件のソート
- リアルタイムシステムで最悪ケースの応答時間を保証する必要がある場合
模範解答の要点:
1. Timsort（言語組み込みの sorted()）
- 安定ソート、O(n log n) 保証、実データに強い
2. 挿入ソート
- ほぼソート済みデータに O(n) で動作
- 1000 件なら O(n^2) でも十分高速
3. 計数ソート
- 値の範囲 k=256 が十分小さい
- O(n + k) = O(n) で 1 億件を線形時間でソート
4. ヒープソート
- O(1) 追加メモリ（インプレース）
- O(n log n) 保証
5. ヒープソートまたは Introsort
- 最悪 O(n log n) が保証される
- クイックソートは最悪 O(n^2) のため不適
問題 2-2: カスタムソートの実装
文字列の配列を「文字列を連結したときに最大の数になる順」にソートする関数を実装せよ。
# 例: ["3", "30", "34"] → ["34", "3", "30"] (34330 が最大)
# 例: ["9", "97", "972"] → ["9", "972", "97"] (997297 が最大)
from functools import cmp_to_key
def largest_number(nums: list) -> str:
"""
数値の文字列配列を、連結した結果が最大になる順にソートする。
比較関数: a+b と b+a を比較し、a+b > b+a なら a を先にする。
この比較関数は全順序の条件を満たすことが証明できる。
"""
str_nums = [str(n) for n in nums]
def compare(a, b):
if a + b > b + a:
return -1
elif a + b < b + a:
return 1
else:
return 0
str_nums.sort(key=cmp_to_key(compare))
# 先頭が 0 の場合（すべて 0）
if str_nums[0] == '0':
return '0'
return ''.join(str_nums)
# --- 動作確認 ---
assert largest_number([3, 30, 34]) == "34330"
assert largest_number([10, 2]) == "210"
assert largest_number([0, 0]) == "0"演習 Level 3: 発展（理論と高度な実装）
問題 3-1: k 個のソート済み配列のマージ
k 個のソート済み配列を 1 つのソート済み配列にマージするアルゴリズムを実装せよ。合計要素数を n とした場合、O(n log k) の計算量を達成すること。
import heapq
def merge_k_sorted_arrays(arrays: list) -> list:
"""
k 個のソート済み配列を O(n log k) でマージする。
最小ヒープを使用して、常に全配列の先頭要素の中から最小値を取り出す。
Args:
arrays: ソート済み配列のリスト
Returns:
マージされた 1 つのソート済み配列
"""
result = []
# (値, 配列のインデックス, 配列内のインデックス) のタプルをヒープに格納
heap = []
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_idx, elem_idx = heapq.heappop(heap)
result.append(val)
# 同じ配列の次の要素をヒープに追加
if elem_idx + 1 < len(arrays[arr_idx]):
next_val = arrays[arr_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))
return result
# --- 動作確認 ---
arrays = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
]
assert merge_k_sorted_arrays(arrays) == [1, 1, 2, 3, 4, 4, 5, 6]問題 3-2: 転倒数の計算
配列の転倒数（inversion count）をマージソートの応用で O(n log n) で計算するアルゴリズムを実装せよ。
def count_inversions(arr: list) -> int:
"""
転倒数を O(n log n) で計算する。
マージソートのマージ操作中に、右側の配列から要素を取る際に
左側の残り要素数が転倒数に加算される。
転倒 (inversion): i < j かつ arr[i] > arr[j] であるペア (i, j)
Args:
arr: 整数のリスト
Returns:
転倒数
"""
if len(arr) <= 1:
return 0
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# 左半分と右半分の転倒数を再帰的に計算
inv_count = count_inversions(left) + count_inversions(right)
# マージしながら分割間の転倒数を計算
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
# left[i:] のすべての要素が right[j] より大きい → 転倒
inv_count += len(left) - i
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
return inv_count
# --- 動作確認 ---
assert count_inversions([1, 2, 3, 4, 5]) == 0 # ソート済み: 転倒なし
assert count_inversions([5, 4, 3, 2, 1]) == 10 # 逆順: n(n-1)/2 = 10
assert count_inversions([2, 4, 1, 3, 5]) == 3 # (2,1), (4,1), (4,3)問題 3-3: Timsort の簡易実装
Timsort の核心部分（run の検出 + 挿入ソートによる短い run の拡張 + マージ）を簡易的に実装せよ。
# ヒント:
# 1. find_runs(): 昇順/降順の run を検出（降順は反転）
# 2. ensure_min_run(): run が minrun 未満なら挿入ソートで拡張
# 3. merge_runs(): run をスタックに積み、条件に従ってマージ
# minrun の計算: n のビット列の上位 6 ビット + 残りビットの OR10. FAQ（よくある質問）
Q1: なぜ教育現場ではバブルソートを教えるのか？
A: バブルソートは、アルゴリズムの基本概念を学ぶための教材として極めて優れている。比較、交換、ループ不変条件、最悪ケース分析、early exit による最適化といった概念を、最も単純な形で体験できる。さらに、バブルソートの非効率さを O(n log n) アルゴリズムと対比することで、アルゴリズムの選択が性能に与える劇的な影響を体感できる。ただし、バブルソートは実務では使用すべきではない。教育目的のみの存在であることを強調しておく。Donald Knuth も "bubble sort seems to have nothing to recommend it, except a catchy name" と述べている。
Q2: クイックソートの最悪ケース O(n^2) は実務で問題にならないのか？
A: 適切なピボット選択戦略を用いれば、最悪ケースに遭遇する確率は極めて低い。ランダムピボット選択の場合、最悪ケースの確率は 1/n! である。さらに、実務で使用される実装はハイブリッド化されている。C++ の Introsort は再帰深度が 2 * log(n) を超えるとヒープソートに切り替え、Rust の pdqsort はパターンを検出して最適な戦略を自動選択する。したがって、自作のクイックソートを使う場合は最悪ケースに注意が必要だが、言語組み込みのソートを使用する限り、この問題は解消されている。
Q3: 10 億件のデータをソートするにはどうすればよいか？
A: データがメインメモリに収まるかどうかで戦略が異なる。メモリに収まる場合は、言語標準のソート（Timsort 等）で十分である。メモリに収まらない場合は外部ソート（External Sort）を使用する。データをメモリに収まるチャンクに分割し、各チャンクをソートしてディスクに書き出し、多方向マージで統合する。分散環境では MapReduce や Apache Spark の sortBy 等のフレームワークが利用できる。これらは内部的にサンプルソートの原理に基づいてデータを分散ノードに振り分け、並列にソートする。
Q4: Python の sorted() と list.sort() の違いは何か？
A: 両者ともに Timsort を使用するが、動作が異なる。sorted() は新しいリストを返す非破壊的な関数であり、任意のイテラブルに適用できる。list.sort() はリストをインプレースで変更する破壊的なメソッドであり、リストオブジェクトにのみ適用できる。メモリ効率を重視する場合は list.sort() を、元のデータを保持したい場合は sorted() を使用する。なお、sorted() は内部的にリストを生成してから list.sort() を呼び出すため、若干のオーバーヘッドがある。
Q5: ソートの「安定性」はどのような場面で重要になるか？
A: 安定性が重要になる典型的な場面は以下の通りである。(1) データベースのクエリ結果を複数のカラムでソートする場合。例えば「まず名前順、次に点数順」というソートは、安定ソートを 2 回適用するだけで実現できる。(2) UI のテーブルソートで、ユーザーがカラムヘッダを順にクリックして多重ソートを行う場合。(3) 基数ソートの内部で各桁のソートに安定ソートを使用する必要がある場合。不安定ソートでは、以前のソート結果が破壊される可能性がある。Python の sorted() と list.sort() は安定ソートであるため、これらの場面で安心して使用できる。
Q6: なぜ O(n) のソートが常に使われないのか？
A: O(n) のソート（計数ソート、基数ソート、バケットソート）には適用条件がある。計数ソートは値の範囲 k が n に対して十分に小さい場合にのみ効率的であり、k >> n では空間・時間ともに無駄が大きい。基数ソートは固定長の整数や文字列にのみ適用可能で、浮動小数点数や可変長オブジェクトには直接適用できない。バケットソートはデータが一様分布に近い場合にのみ効率的である。さらに、これらのアルゴリズムは比較関数をカスタマイズできないため、複雑なソート基準には対応できない。汎用性の観点から、比較ベースのソートが標準として広く使用されている。
11. 計算量の直感的理解 ― ソートにかかる時間の目安
実際のプログラミングにおいて、データ量に対するソートの所要時間を概算することは重要である。以下の表は、各計算量クラスが具体的にどの程度の処理量になるかの目安を示す（1 秒あたり約 10^8 ~ 10^9 回の基本操作を想定）。
+==========+==============+==============+==============+==============+
| n | O(n) | O(n log n) | O(n^2) | O(n^2) 比率 |
| | 操作回数 | 操作回数 | 操作回数 | vs O(n logn) |
+==========+==============+==============+==============+==============+
| 10 | 10 | ~33 | 100 | 3x |
+----------+--------------+--------------+--------------+--------------+
| 100 | 100 | ~664 | 10,000 | 15x |
+----------+--------------+--------------+--------------+--------------+
| 1,000 | 1,000 | ~9,966 | 1,000,000 | 100x |
+----------+--------------+--------------+--------------+--------------+
| 10,000 | 10,000 | ~132,877 | 100,000,000 | 752x |
+----------+--------------+--------------+--------------+--------------+
| 100,000 | 100,000 | ~1,660,964 | 10^10 | 6,020x |
+----------+--------------+--------------+--------------+--------------+
| 1,000,000| 1,000,000 | ~19,931,569 | 10^12 | 50,172x |
+----------+--------------+--------------+--------------+--------------+
n = 100 万のとき、O(n^2) は O(n log n) に比べて約 5 万倍の操作が必要になる。これが「バブルソートで 100 万件のデータをソートしてはならない」理由である。
12. ソートアルゴリズムの歴史的背景
ソートアルゴリズムの歴史は、コンピュータサイエンスの歴史そのものと深く結びついている。
1945 John von Neumann がマージソートを EDVAC のプログラムとして記述
（最初の計算機プログラムの一つ）
1959 Donald Shell がシェルソートを発表
（ギャップ付き挿入ソートの概念を導入）
1960 C.A.R. Hoare がクイックソートを発表
（「20世紀で最も重要なアルゴリズムの一つ」と評される）
1964 J.W.J. Williams がヒープソートを発表
（ヒープデータ構造の導入と同時）
1969 Harold H. Seward が計数ソートと基数ソートを形式化
1973 Donald Knuth が "The Art of Computer Programming" Vol.3 を出版
（ソートと探索の百科全書的な著作）
1993 Ingo Wegener がヒープソートの最悪ケース比較回数の下限を証明
1997 David Musser が Introsort を提案
（C++ STL に採用）
2002 Tim Peters が Timsort を設計
（Python の標準ソートとして採用）
2009 Java 7 で Vladimir Yaroslavskiy の Dual-Pivot Quicksort を採用
2021 Orson Peters が pdqsort を発表
（Rust, Go に採用）
FAQ
Q1: このトピックを学ぶ上で最も重要なポイントは何ですか？
実践的な経験を積むことが最も重要です。理論だけでなく、実際にコードを書いて動作を確認することで理解が深まります。
Q2: 初心者がよく陥る間違いは何ですか？
基礎を飛ばして応用に進むことです。このガイドで説明している基本概念をしっかり理解してから、次のステップに進むことをお勧めします。
Q3: 実務ではどのように活用されていますか？
このトピックの知識は、日常的な開発業務で頻繁に活用されます。特にコードレビューやアーキテクチャ設計の際に重要になります。
まとめ
本章では、ソートアルゴリズムを基礎から応用まで体系的に解説した。要点を以下にまとめる。
核心的な理解
-
比較ベースのソートには Omega(n log n) の理論的下限がある。マージソート、ヒープソート、Timsort はこの下限に漸近的に到達する最適なアルゴリズムである。
-
非比較ベースのソートはこの下限を打破できるが、適用条件（整数、固定範囲等）がある。計数ソートは O(n + k)、基数ソートは O(d(n + k)) で動作する。
-
実務では言語組み込みのソートを使用するのが最善である。Timsort、Introsort、pdqsort 等のハイブリッドソートは、理論的保証と実用的性能を両立している。
-
アルゴリズムの選択はデータの特性に依存する。データの量、分布、既存の整列度、メモリ制約、安定性の要否を考慮して判断する。
アルゴリズム選択の指針
データが小規模 (n < 50) → 挿入ソート
データがほぼソート済み → 挿入ソート or Timsort
安定性が必要 → マージソート or Timsort
メモリ制約が厳しい → ヒープソート
最悪計算量の保証が必要 → ヒープソート or Introsort
整数で値の範囲が小さい → 計数ソート
固定長の整数/文字列 → 基数ソート
汎用（特別な制約なし） → 言語組み込み (Timsort 等)
メモリに収まらない巨大データ → 外部ソート
13. ソートに関する重要な定理と補足
13.1 最適な比較回数
n 個の要素をソートするための「最小比較回数」は、情報理論的下限 ceil(log_2(n!)) で与えられる。これは決定木の高さの下限そのものである。
n = 1: 0 回（比較不要）
n = 2: 1 回 ceil(log_2(2!)) = ceil(1) = 1
n = 3: 3 回 ceil(log_2(3!)) = ceil(2.58) = 3
n = 4: 5 回 ceil(log_2(4!)) = ceil(4.58) = 5
n = 5: 7 回 ceil(log_2(5!)) = ceil(6.91) = 7
n = 10: 22 回 ceil(log_2(10!)) = ceil(21.79)= 22
n = 12: 29 回 ceil(log_2(12!)) = ceil(28.84)= 29
Ford-Johnson アルゴリズム（merge-insertion sort, 1959）:
小さい n に対して比較回数が最小となるソートアルゴリズム。
n <= 12 までは最適であることが証明されている。
実用的ではないが、理論的に重要。
13.2 ソートネットワーク
ソートネットワークは、データに依存しない固定的な比較・交換パターンでソートを行う計算モデルである。並列計算との親和性が高い。
n = 4 のソートネットワーク（最適: 5 比較器）
入力 ──●──────●──────── 出力(最小)
| |
●──●──────●───── 出力
| |
●──●──────●───── 出力
| |
入力 ──●──────●──────── 出力(最大)
各 ● は比較器（比較して必要なら交換する）。
左から右に信号が流れ、各列の比較器は並列に実行可能。
深さ（列数）= 並列ステップ数
AKS ネットワーク（Ajtai-Komlos-Szemeredi, 1983）:
O(n log n) の比較器数、O(log n) の深さを持つ
ソートネットワークが存在することを証明。
ただし定数倍が巨大で非実用的。
Batcher の奇偶マージネットワーク:
O(n log^2 n) の比較器数、O(log^2 n) の深さ。
実用的な並列ソートに使用される。13.3 下限を超えるために ― 非比較ソートの情報理論的解釈
比較ベースのソートでは、1 回の比較で得られる情報量が 1 ビットに制限される。n! 通りの順列を区別するには log_2(n!) ビットの情報が必要であり、これが Omega(n log n) の下限の本質である。
非比較ソートは、1 回の操作で 1 ビット以上の情報を取得する。例えば計数ソートでは、要素の値を読み取ることで log_2(k) ビットの情報を一度に得る。これにより、比較下限を打破できる。
13.4 ソートの下限と計算モデル
+========================+=============================+===============+
| 計算モデル | ソートの下限 | 代表的手法 |
+========================+=============================+===============+
| 比較モデル | Omega(n log n) | マージ, QS |
+------------------------+-----------------------------+---------------+
| 整数 RAM モデル | Omega(n * sqrt(log log n)) | Han-Thorup |
| (word size w = O(logn))| | (2002, 理論的)|
+------------------------+-----------------------------+---------------+
| 外部メモリモデル | Omega((n/B)*log_{M/B}(n/B)) | 多方向マージ |
+------------------------+-----------------------------+---------------+
| 並列比較モデル | Omega(log n) 深さ | AKS ネット |
| (p = n プロセッサ) | | ワーク |
+------------------------+-----------------------------+---------------+
14. 実装上の工夫と最適化テクニック
14.1 ソートの前処理と後処理
# --- 実装テクニック: センチネル値 ---
# マージ操作で番兵（sentinel）を使うと境界チェックを削除できる
def merge_with_sentinel(arr, left, mid, right):
"""番兵を使ったマージ操作。境界チェックが不要になる。"""
L = arr[left:mid + 1] + [float('inf')] # 番兵（無限大）
R = arr[mid + 1:right + 1] + [float('inf')]
i = j = 0
for k in range(left, right + 1):
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 114.2 Tail Call Elimination によるクイックソートの最適化
def quicksort_optimized(arr: list, low: int, high: int) -> None:
"""
末尾呼び出し最適化版クイックソート。
短い方の部分配列を再帰で処理し、長い方をループで処理する。
→ スタック使用量を O(log n) に保証。
"""
while low < high:
pivot_idx = _partition_random(arr, low, high)
# 短い方を再帰、長い方をループで処理
if pivot_idx - low < high - pivot_idx:
quicksort_optimized(arr, low, pivot_idx - 1)
low = pivot_idx + 1 # 末尾再帰をループに変換
else:
quicksort_optimized(arr, pivot_idx + 1, high)
high = pivot_idx - 1 # 末尾再帰をループに変換14.3 3-way パーティション（Dutch National Flag）
重複が多いデータでクイックソートの性能を改善する。ピボットと等しい要素を中央にまとめる。
def quicksort_3way(arr: list, low: int, high: int) -> None:
"""
3-way パーティション版クイックソート。
Dijkstra の Dutch National Flag アルゴリズムを使用。
重複が多いデータで O(n log n) → O(n) に改善される場合がある。
"""
if low >= high:
return
# 3-way partition: [< pivot | == pivot | > pivot]
lt = low # arr[low..lt-1] < pivot
gt = high # arr[gt+1..high] > pivot
i = low # arr[lt..i-1] == pivot
pivot = arr[low]
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[gt], arr[i] = arr[i], arr[gt]
gt -= 1
# i は進めない（交換された要素の確認が必要）
else:
i += 1
# arr[lt..gt] はすべて pivot と等しい → ソート不要
quicksort_3way(arr, low, lt - 1)
quicksort_3way(arr, gt + 1, high)
# --- 動作確認 ---
test = [4, 2, 4, 1, 4, 3, 4, 2]
quicksort_3way(test, 0, len(test) - 1)
assert test == [1, 2, 2, 3, 4, 4, 4, 4]15. ソートの応用問題集
ソートを道具として使う応用的な問題をいくつか紹介する。ソートアルゴリズム自体の知識だけでなく、「ソートを活用して別の問題を効率的に解く」視点が重要である。
15.1 交差区間の検出（Interval Overlap）
def has_overlap(intervals: list) -> bool:
"""
区間のリストに重複があるかを判定する。
区間を開始点でソートし、隣接する区間の重複を確認する。
計算量: O(n log n)（ソートが支配的）
Args:
intervals: [(start, end), ...] のリスト
Returns:
重複がある場合 True
"""
if len(intervals) <= 1:
return False
# 開始点でソート（同じ開始点なら終了点で）
sorted_intervals = sorted(intervals, key=lambda x: (x[0], x[1]))
for i in range(1, len(sorted_intervals)):
# 前の区間の終了点 > 現在の区間の開始点 なら重複
if sorted_intervals[i - 1][1] > sorted_intervals[i][0]:
return True
return False
assert has_overlap([(1, 5), (3, 7), (8, 10)]) == True # (1,5) と (3,7) が重複
assert has_overlap([(1, 3), (4, 6), (7, 9)]) == False # 重複なし15.2 最近接点対問題への応用
2次元平面上の n 個の点から最も近い点のペアを見つける問題。
ナイーブ: O(n^2) — 全ペアの距離を計算
分割統治法 + ソート: O(n log n)
手順:
1. 点を x 座標でソート: O(n log n)
2. 中央で左右に分割
3. 左右それぞれで最近接点対を再帰的に求める
4. 分割線をまたぐ点対を確認（y 座標でソートされた帯状領域を走査）
5. 全体の最小距離を返す
ソートが問題の構造化に不可欠な役割を果たす好例。
15.3 ソートを用いた計算幾何の基本操作
def closest_pair_1d(points: list) -> tuple:
"""
1次元上の最近接点対を O(n log n) で求める。
ソート後に隣接要素の差を確認するだけでよい。
"""
if len(points) < 2:
return None
sorted_pts = sorted(points)
min_dist = float('inf')
closest = None
for i in range(1, len(sorted_pts)):
dist = sorted_pts[i] - sorted_pts[i - 1]
if dist < min_dist:
min_dist = dist
closest = (sorted_pts[i - 1], sorted_pts[i])
return closest
assert closest_pair_1d([7, 1, 3, 10, 4]) == (3, 4)16. ソートのベンチマーク指針
ソートアルゴリズムの性能を正しく評価するためのベンチマーク指針を以下に示す。
16.1 テストすべき入力パターン
+=============================+==========================================+
| パターン | 目的 |
+=============================+==========================================+
| ランダム (一様分布) | 平均的な性能を測定 |
+-----------------------------+------------------------------------------+
| ソート済み (昇順) | 最良ケースの確認 |
+-----------------------------+------------------------------------------+
| 逆順 (降順) | 最悪ケースの候補 |
+-----------------------------+------------------------------------------+
| すべて同一の値 | 重複の処理性能 |
+-----------------------------+------------------------------------------+
| ほぼソート済み | 適応性の確認 |
| (少数のランダム交換) | |
+-----------------------------+------------------------------------------+
| パイプオルガン | [1,2,...,n,...,2,1] |
| (山型) | 部分的な整列の処理 |
+-----------------------------+------------------------------------------+
| 少数のユニークな値 | 重複の多いデータへの対処 |
+-----------------------------+------------------------------------------+
| 先頭/末尾のみ乱れ | 局所的な乱れの処理 |
+-----------------------------+------------------------------------------+
16.2 ベンチマークの注意点
- ウォームアップ: JIT コンパイルやキャッシュの影響を排除するため、測定前にウォームアップ実行を行う
- 複数回測定: 統計的に有意な結果を得るため、同じ条件で複数回測定し中央値を取る
- 入力のコピー: インプレースソートの場合、同じ入力を使い回さないようにコピーを作成する
- GC の影響: ガベージコレクションの影響を考慮する（Python では
gc.disable()で一時的に無効化できる） - データサイズの段階的変化: n を 10, 100, 1000, ... と段階的に変化させて、計算量の傾向を確認する
次に読むべきガイド
参考文献
-
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." 4th Edition, MIT Press, 2022. Chapters 6-9.（ソートアルゴリズムの理論的基盤と証明を網羅した標準的教科書）
-
Sedgewick, R. and Wayne, K. "Algorithms." 4th Edition, Addison-Wesley, 2011. Chapter 2.（実装指向のソートアルゴリズム解説。Java によるコード例が豊富）
-
Knuth, D. E. "The Art of Computer Programming, Volume 3: Sorting and Searching." 2nd Edition, Addison-Wesley, 1998.（ソートと探索の百科全書。歴史的背景と数学的解析が詳細）
-
Peters, T. "Timsort description." CPython Developer Documentation, 2002. https://github.com/python/cpython/blob/main/Objects/listsort.txt（Timsort の設計文書。実装上の工夫が詳述されている）
-
Musser, D. "Introspective Sorting and Selection Algorithms." Software: Practice and Experience, 27(8), pp. 983-993, 1997.（Introsort の原論文。クイックソートの最悪ケースを回避する手法）
-
Peters, O. "Pattern-defeating Quicksort." arXiv:2106.05123, 2021.（pdqsort の論文。データパターンの検出と適応的な戦略切替）