「データを並べ替える」——たったそれだけの話が、なぜ70年以上も研究され続けているのか。
この記事では、ソートアルゴリズムの歴史、発明者のエピソード、計算量、実装コードを徹底的に掘り下げます。
定番から玄人枠、そしてアルゴリズム界のジョークまで、”過剰”なほどに解説します。
- 1. なぜソートを学ぶのか
- 2. ソートの基礎知識
- 3. 計算量比較表
- 4. 定番ソートアルゴリズム
- 5. 実務の王者たち
- 6. 玄人向けソート
- 7. ジョークソート
- 8. 実測ベンチマーク
- 9. まとめ
- 10. 参考文献
1. なぜソートを学ぶのか
ソートは「設計入門」である
「要素を小さい順に並べ替える」——単純に見えるこの問題が、実は奥深い設計判断の宝庫です。
現場では、こんな問いが潜んでいます：
- 安定性は必要？ 同じ値の相対順序を守りたいか
- メモリ制約は？ 補助領域を使えるか、in-placeで済ませたいか
- 入力データの性質は？ ほぼ整列済み？完全ランダム？
- 最悪ケースを許容できる？ O(n²)が発生しても構わないか
- 並列化する？ GPU・SIMDを活用するか
同じ「ソート」でも、これらの答えによって最適解は変わります。だからソートは、アルゴリズム入門であると同時に設計思想の入門でもあるのです。
ソートの歴史は計算機の歴史
ソートアルゴリズムの歴史は、コンピュータの歴史そのものです。
- 1890年代：Herman Hollerithがパンチカードの基数ソートを発明。これがIBM創業の礎となる
- 1945年：John von Neumannがマージソートを考案。最初期のコンピュータプログラムの一つ
- 1956年：Edward Harry Friendがバブルソートを論文で発表
- 1959年：Tony Hoareがモスクワでクイックソートを発明。ロシア語翻訳プロジェクトがきっかけ
- 1964年：J.W.J. Williamsがヒープソートとバイナリヒープを発明
- 2002年：Tim PetersがTimsortを開発。Pythonの標準ソートに採用
2. ソートの基礎知識
2-1. 時間計算量（Time Complexity）
アルゴリズムの「速さ」を表す指標。入力サイズnに対して、処理にかかる時間がどう増えるかを示します。
| 表記 | 意味 | 具体例 |
|---|---|---|
| O(1) | 定数時間 | 配列の要素アクセス |
| O(log n) | 対数時間 | 二分探索 |
| O(n) | 線形時間 | 配列の全要素走査 |
| O(n log n) | 準線形時間 | 効率的なソート |
| O(n²) | 二乗時間 | 単純なソート |
| O(n!) | 階乗時間 | 全順列の列挙 |
比較ソートの理論下限：比較に基づくソートは、最悪でもΩ(n log n)の比較が必要です。これは情報理論的に証明されています。
2-2. 空間計算量（Space Complexity）
アルゴリズムが使用する追加メモリの量。
- O(1)：定数個の変数のみ（in-place）
- O(log n)：再帰スタック分
- O(n)：入力と同サイズの補助配列
注意：「in-place」と言っても、再帰呼び出しのスタックは別途必要な場合があります。
2-3. 安定性（Stability）
安定ソートとは、同じキーを持つ要素の相対順序が保たれるソートです。
例えば、(商品名, 価格)のデータを価格でソートする場合：
- 安定：同じ価格の商品は元の順序を維持
- 不安定：同じ価格の商品の順序は不定
安定性が重要な場面：複数キーでの段階的ソート、ユーザーの並び順を尊重したいUI
2-4. in-place（原位置ソート）
追加のメモリをO(1)しか使わないソート。メモリ効率は良いが、実装が複雑になりがちです。
2-5. 適応性（Adaptivity）
入力データの「ほぼ整列具合」を活用できるかどうか。適応的なアルゴリズムは、ほぼ整列済みのデータで高速に動作します。
2-6. キャッシュ効率（Cache Efficiency）
現代のCPUはキャッシュを活用します。連続したメモリアクセスが多いアルゴリズムは高速です。
- 局所性が良い：マージソート、クイックソート
- 局所性が悪い：ヒープソート（木構造を飛び回る）
LaMarcaらの1997年の研究は、ソートアルゴリズムのキャッシュ影響を本格的に分析した先駆けです。
3. 計算量比較表
| アルゴリズム | 最良 | 平均 | 最悪 | 空間 | 安定 | 適応的 | 発明年 |
|---|---|---|---|---|---|---|---|
| バブルソート | O(n) | O(n²) | O(n²) | O(1) | ✓ | ✓ | 1956 |
| 選択ソート | O(n²) | O(n²) | O(n²) | O(1) | ✗ | ✗ | – |
| 挿入ソート | O(n) | O(n²) | O(n²) | O(1) | ✓ | ✓ | – |
| シェルソート | O(n log n) | O(n^1.25)〜 | O(n²) | O(1) | ✗ | ✓ | 1959 |
| マージソート | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ | ✗ | 1945 |
| クイックソート | O(n log n) | O(n log n) | O(n²) | O(log n) | ✗ | ✗ | 1959 |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ | ✗ | 1964 |
| カウントソート | O(n+k) | O(n+k) | O(n+k) | O(k) | ✓ | – | – |
| 基数ソート | O(nk) | O(nk) | O(nk) | O(n+k) | ✓ | – | 1887 |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | ✓ | ✓ | 2002 |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | ✗ | ✗ | 1997 |
4. 定番ソートアルゴリズム
4-1. バブルソート（Bubble Sort）
発明と歴史
バブルソートの最初の記述は、1956年の数学者・アクチュアリーであるEdward Harry Friendの論文「Sorting on Electronic Computer Systems」です。ACM Journalの第3巻第3号に掲載されました。
当時は「sorting by exchange（交換によるソート）」と呼ばれていました。「バブルソート」という名前の正確な起源は不明ですが、1959年頃には使われ始めていたようです。
Knuthの辛辣な評価
Donald Knuthは『The Art of Computer Programming』で有名な一文を残しています：
「バブルソートには、キャッチーな名前と興味深い理論的問題につながること以外に、推奨できる点がない」
教育者Owen Astrachanもバブルソートを教えることを強く批判し、「もう教えるべきではない」と主張しています。
アルゴリズム
隣同士を比較し、逆順なら交換。これを端まで繰り返します。
def bubble_sort(a):
"""バブルソート：隣接要素を比較・交換"""
a = a[:]
n = len(a)
for i in range(n):
swapped = False
for j in range(0, n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 最適化：交換がなければ終了
break
return a特徴
- 亀と兎問題：大きい値は素早く右へ移動（兎）するが、小さい値は左へ移動するのが遅い（亀）
- 唯一の利点：ほぼ整列済みデータで高速。ポリゴン塗りつぶしアルゴリズムで使われることも
4-2. シェーカーソート（Cocktail Shaker Sort）
バブルソートの「亀問題」を改善。往復で走査することで、小さい値の移動を速めます。
def cocktail_shaker_sort(a):
"""シェーカーソート：双方向バブルソート"""
a = a[:]
left, right = 0, len(a) - 1
while left < right:
swapped = False
# 左から右へ
for i in range(left, right):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
right -= 1
# 右から左へ
for i in range(right, left, -1):
if a[i - 1] > a[i]:
a[i - 1], a[i] = a[i], a[i - 1]
swapped = True
left += 1
if not swapped:
break
return a4-3. コムソート（Comb Sort）
発明
1980年にWłodzimierz Dobosiewiczが発表し、1991年にStephen LaceyとRichard BoxがByte誌で「A Fast, Easy Sort」として広めました。
アイデア
バブルソートの「亀」を倒すため、gap（間隔）を使います。最初は大きなgapで遠距離比較し、徐々にgapを縮めます。
def comb_sort(a, shrink=1.3):
"""コムソート：gap付きバブルソート"""
a = a[:]
n = len(a)
gap = n
swapped = True
while gap > 1 or swapped:
gap = int(gap / shrink) if gap > 1 else 1
swapped = False
for i in range(0, n - gap):
if a[i] > a[i + gap]:
a[i], a[i + gap] = a[i + gap], a[i]
swapped = True
return a縮小率1.3は経験的に最適とされています。
4-4. 選択ソート（Selection Sort）
「最小値を見つけて先頭に置く」を繰り返すシンプルなアルゴリズム。
特徴
- 比較回数は常にn(n-1)/2で入力に鈍感
- 交換回数は最大n-1回で少ない
- swapコストが高い環境で有利なことも
def selection_sort(a):
"""選択ソート：最小値を選んで先頭へ"""
a = a[:]
n = len(a)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
return a4-5. 挿入ソート（Insertion Sort）
「左側は整列済み」と仮定し、次の要素を正しい位置に挿入。トランプの手札を整理する動作に似ています。
現場での重要性
挿入ソートは小さい配列で非常に高速です。そのため、Timsort・Introsort・クイックソートなど多くの実用アルゴリズムで、小規模パーティションの仕上げに使われます。
def insertion_sort(a):
"""挿入ソート：整列済み部分に挿入"""
a = a[:]
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a4-6. シェルソート（Shellsort）
発明者：Donald L. Shell（1959年）
Donald Shellはシンシナティ大学で数学の博士号を取得した直後の1959年7月、ACM Communicationsにシェルソートを発表しました。
General Electric社でジェットエンジンの性能計算プログラムを開発していた彼は、挿入ソートの弱点に着目。「遠距離要素の比較」というアイデアで改良を施しました。
興味深いことに、一時期「Shell-Metzner sort」という誤った名称が広まりましたが、Marlene Metzner本人が「私はこのソートと何の関係もない」と否定しています。
アルゴリズム
挿入ソートを「gap」を使って遠距離に適用し、gapを縮めながら繰り返します。
def shell_sort(a):
"""シェルソート：gap付き挿入ソート"""
a = a[:]
# Ciuraの数列：経験的に高速
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
n = len(a)
for gap in gaps:
for i in range(gap, n):
tmp = a[i]
j = i
while j >= gap and a[j - gap] > tmp:
a[j] = a[j - gap]
j -= gap
a[j] = tmp
return agap数列の研究
シェルソートの計算量はgap数列に依存し、最適な数列は未解決問題です。
| 研究者 | 数列 | 最悪計算量 |
|---|---|---|
| Shell (1959) | n/2, n/4, … | O(n²) |
| Hibbard (1963) | 2^k – 1 | O(n^1.5) |
| Pratt (1971) | 2^p × 3^q | O(n log² n) |
| Sedgewick (1986) | 複雑な式 | O(n^4/3) |
| Ciura (2001) | 1,4,10,23,57… | 経験的に最速 |
4-7. マージソート（Merge Sort）
発明者：John von Neumann（1945年）
マージソートは史上最初のソートアルゴリズムの一つです。
天才数学者John von Neumannが1945年、EDVACコンピュータの設計中に考案しました。Herman Goldstineとの共著で1948年に詳細が発表されています。
Donald Knuthが1970年の論文「Von Neumann’s First Computer Program」でこの歴史を詳しく調査しました。
アルゴリズム
分割統治法の典型例。配列を半分に分け、それぞれをソートし、マージします。
def merge_sort(a):
"""マージソート：分割統治の典型"""
a = a[:]
def merge(left, right):
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
def sort(x):
if len(x) <= 1:
return x
mid = len(x) // 2
return merge(sort(x[:mid]), sort(x[mid:]))
return sort(a)特徴
- 最悪でもO(n log n)を保証
- 安定
- 外部ソートに最適：磁気テープ時代から活躍
- 欠点：O(n)の補助メモリが必要
4-8. クイックソート（Quicksort）
発明者：Tony Hoare（1959年）
C.A.R. Hoare（通称Tony Hoare）は1959年、モスクワ大学への留学中にクイックソートを発明しました。
当時26歳だった彼は、National Physical Laboratoryの機械翻訳プロジェクトに携わっていました。ロシア語の単語を辞書順にソートする必要があり、最初は挿入ソートを考えましたが「遅すぎる」と気づき、新しいアイデアを思いつきました。
イギリスに帰国後、上司からシェルソートの実装を依頼されたとき、Hoareは「もっと速いアルゴリズムを知っている」と主張。上司は6ペンス硬貨を賭けましたが、結局Hoareの勝ちでした。
1961年、ALGOL 60の再帰機能を使って論文を発表。Jon Bentleyは後にクイックソートを「今まで書いた中で最も美しいコード」と称しました。
Hoareは1980年にチューリング賞を受賞。また「10億ドルの間違い」として知られるnull参照の発明者でもあります。
アルゴリズム
ピボットを選び、それより小さい要素と大きい要素に分割。再帰的に繰り返します。
def quick_sort(a):
"""クイックソート：分割統治の王様"""
a = a[:]
stack = [(0, len(a) - 1)]
while stack:
lo, hi = stack.pop()
if lo >= hi:
continue
# Lomutoパーティション
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
# 大きい側を先にpush（スタック深さを抑える）
if i - 1 - lo > hi - (i + 1):
stack.append((lo, i - 1))
stack.append((i + 1, hi))
else:
stack.append((i + 1, hi))
stack.append((lo, i - 1))
return a最悪ケースO(n²)問題
クイックソートの弱点は、ピボット選択が悪いと最悪O(n²)になること。
- 整列済み配列 + 先頭/末尾ピボット → 最悪ケース
- 「median-of-3 killer」という意地悪な入力も存在
この問題を解決するのがIntrosort（後述）です。
4-9. ヒープソート（Heap Sort）
発明者：J.W.J. Williams（1964年）
John William Joseph Williams（通称Bill Williams）は1964年、ACM Communicationsに「Algorithm 232: Heapsort」を発表しました。
彼はイギリスのElliot Brothers社でプログラマーとして働いており、Tony Hoareと同じ会社でした。ヒープソートの発明と同時に、バイナリヒープというデータ構造も導入しました。
同年、Robert W. Floydがin-place版の改良を発表。これが現在の標準的な実装の基礎となっています。
アルゴリズム
配列をヒープ（完全二分木）として解釈し、最大値を取り出しながらソートします。
def heap_sort(a):
"""ヒープソート：ヒープ構造を活用"""
a = a[:]
n = len(a)
def sift_down(i, size):
while True:
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < size and a[left] > a[largest]:
largest = left
if right < size and a[right] > a[largest]:
largest = right
if largest == i:
break
a[i], a[largest] = a[largest], a[i]
i = largest
# ヒープ構築（Floyd法：O(n)）
for i in range(n // 2 - 1, -1, -1):
sift_down(i, n)
# 最大値を末尾に移動
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift_down(0, end)
return a特徴
- 最悪でもO(n log n)を保証
- in-place：O(1)の追加メモリ
- 欠点：キャッシュ局所性が悪い（木を飛び回る）
- 実測ではクイックソートの2〜5倍遅いことが多い
4-10. カウントソート・基数ソート
比較を使わないソート。整数など値域が限られた場合に威力を発揮し、O(n log n)の壁を破ることができます。
カウントソート
def counting_sort(a, max_value=None):
"""カウントソート：値の出現回数をカウント"""
if not a:
return []
if max_value is None:
max_value = max(a)
count = [0] * (max_value + 1)
for x in a:
count[x] += 1
result = []
for value, cnt in enumerate(count):
result.extend([value] * cnt)
return result基数ソート（LSD）
def radix_sort_lsd(a, base=10):
"""基数ソート（LSD）：桁ごとにカウントソート"""
a = a[:]
if not a:
return a
max_val = max(a)
exp = 1
while max_val // exp > 0:
# 各桁でカウントソート
count = [0] * base
output = [0] * len(a)
for x in a:
digit = (x // exp) % base
count[digit] += 1
for i in range(1, base):
count[i] += count[i - 1]
for i in range(len(a) - 1, -1, -1):
x = a[i]
digit = (x // exp) % base
count[digit] -= 1
output[count[digit]] = x
a = output
exp *= base
return a基数ソートの歴史
驚くべきことに、基数ソートは最古のソートアルゴリズムかもしれません。1887年、Herman Hollerithがアメリカ国勢調査のためにパンチカードソート機械を開発。この機械は基数ソートの原理を使っていました。
Hollerithは後にTabulating Machine Companyを設立。これが1924年にIBMとなります。つまり、基数ソートはIBM創業の礎でもあるのです。
5. 実務の王者たち
5-1. Timsort
発明者：Tim Peters（2002年）
Tim PetersはPythonコミュニティの伝説的人物です。彼は「Zen of Python」（PEP 20）の作者としても知られています。
2002年、PetersはPythonの標準ソートを改善するためにTimsortを開発しました。彼の洞察は：
「ほとんどのソートアルゴリズムは教室で生まれ、実世界のデータ向けに設計されていない」
現実のデータはランダムではなく、部分的に整列していることが多い。Timsortはこの性質を徹底的に活用します。
採用実績
- Python（2.3以降、3.11からはPowersort）
- Java SE 7以降
- Android
- V8 JavaScript Engine（Chrome, Node.js）
- GNU Octave
- Swift
核となるアイデア
1. run（既存の整列部分）の検出
配列を走査し、すでに整列している部分（run）を見つけます。降順のrunは反転して昇順にします。
2. minrunによる補強
短いrunは効率が悪いので、挿入ソートで最低限の長さ（minrun）まで伸ばします。
3. マージスタックの不変条件
runをスタックに積み、特定の条件を満たさなくなったらマージ。これによりバランスの取れたマージを保証します。
4. Galloping mode
マージ中、片方が連続して勝つ場合は二分探索で「ごっそり移動」。
2015年のバグ発見
オランダとドイツの研究者が、形式検証ツールKeYを使ってTimsortの実装にバグを発見しました。スタックサイズの見積もりが不十分で、特定の入力でスタックオーバーフローが起きる可能性がありました。Python、Java、Androidで修正されています。
5-2. Introsort
発明者：David Musser（1997年）
David R. MusserはRensselaer Polytechnic Instituteの教授で、C++ STLの設計者Alexander Stepanovの協力者でもありました。
1997年の論文「Introspective Sorting and Selection Algorithms」で、クイックソートの最悪ケース問題への「シンプルな解決策」を提示しました。
アイデア
- クイックソートで開始（平均が速い）
- 再帰の深さを監視
- 深くなりすぎたらヒープソートに切り替え（最悪O(n²)を回避）
- 小さいパーティションは挿入ソートで仕上げ
「自分自身を観察する」からintrospective（内省的）という名前です。
def introsort(a, threshold=16):
"""Introsort：自己観察型ソート"""
a = a[:]
n = len(a)
if n <= 1:
return a
max_depth = 2 * (n.bit_length() - 1) # 約 2*log2(n)
def insertion_range(lo, hi):
for i in range(lo + 1, hi + 1):
key = a[i]
j = i - 1
while j >= lo and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
def heapsort_range(lo, hi):
# [lo, hi]の範囲をヒープソート
size = hi - lo + 1
def sift(i, heap_size):
while True:
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < heap_size and a[lo + left] > a[lo + largest]:
largest = left
if right < heap_size and a[lo + right] > a[lo + largest]:
largest = right
if largest == i:
break
a[lo + i], a[lo + largest] = a[lo + largest], a[lo + i]
i = largest
for i in range(size // 2 - 1, -1, -1):
sift(i, size)
for end in range(size - 1, 0, -1):
a[lo], a[lo + end] = a[lo + end], a[lo]
sift(0, end)
def partition(lo, hi):
# median-of-3でピボット選択
mid = (lo + hi) // 2
if a[mid] < a[lo]:
a[lo], a[mid] = a[mid], a[lo]
if a[hi] < a[lo]:
a[lo], a[hi] = a[hi], a[lo]
if a[hi] < a[mid]:
a[mid], a[hi] = a[hi], a[mid]
pivot = a[mid]
a[mid], a[hi] = a[hi], a[mid]
i = lo
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return i
def intro(lo, hi, depth):
while hi - lo + 1 > threshold:
if depth == 0:
heapsort_range(lo, hi)
return
depth -= 1
p = partition(lo, hi)
if p - lo < hi - p:
intro(lo, p - 1, depth)
lo = p + 1
else:
intro(p + 1, hi, depth)
hi = p - 1
insertion_range(lo, hi)
intro(0, n - 1, max_depth)
return a採用実績
- C++ STL
std::sort（SGI実装から） - .NET
Array.Sort - Java 14以降（一部の型で）
Musserの実験では、「median-of-3 killer」という意地悪な入力に対して、Introsortは通常のクイックソートの1/200の時間で完了しました。
6. 玄人向けソート
6-1. Bitonic Sort（ソーティングネットワーク）
発明者：Ken Batcher（1968年）
Bitonic Sortはソーティングネットワークの一種で、比較の順序がデータに依存しないという特徴があります。
これはGPUやSIMD命令で並列化する際に非常に有利です。条件分岐がないため、パイプラインストールが起きません。
def bitonic_sort(a, ascending=True):
"""Bitonicソート：並列処理向け"""
a = a[:]
n = len(a)
if n <= 1:
return a
# 2のべき乗にパディング
m = 1 << (n - 1).bit_length()
pad_val = max(a) + 1 if a else 0
a.extend([pad_val] * (m - n))
def compare_and_swap(i, j, dir_up):
if (a[i] > a[j]) == dir_up:
a[i], a[j] = a[j], a[i]
def bitonic_merge(lo, cnt, dir_up):
if cnt > 1:
k = cnt // 2
for i in range(lo, lo + k):
compare_and_swap(i, i + k, dir_up)
bitonic_merge(lo, k, dir_up)
bitonic_merge(lo + k, k, dir_up)
def bitonic_rec(lo, cnt, dir_up):
if cnt > 1:
k = cnt // 2
bitonic_rec(lo, k, True)
bitonic_rec(lo + k, k, False)
bitonic_merge(lo, cnt, dir_up)
bitonic_rec(0, m, ascending)
return a[:n]計算量
- 比較器の数：O(n log² n)
- 並列段数：O(log² n)
6-2. Smoothsort
発明者：Edsger W. Dijkstra（1981年）
Dijkstraといえばダイクストラ法やセマフォで有名ですが、彼はSmoothsortも発明しています。
Smoothsortは「ほぼ整列済みなら線形に近い」かつ「最悪でもO(n log n)」を目指したヒープソートの変種です。Leonardo数（1, 1, 3, 5, 9, 15, 25…）に基づく「森」構造を使います。
Dijkstraは3週間かけてこのアルゴリズムを開発し、完成時に「よかった」と安堵したそうです。
実装が複雑なため、実務ではあまり使われませんが、理論的に美しいアルゴリズムとして知られています。
6-3. Patience Sort
由来：ソリティア（一人遊びカードゲーム）
Patience Sortは、ソリティアの「パイル（山）を作る」動作に由来します。
面白い性質として、最長増加部分列（LIS）の長さがパイルの数と一致します。
def patience_sort(a):
"""Patience Sort：カードゲーム由来"""
import bisect
import heapq
n = len(a)
if n <= 1:
return a[:]
items = [(a[i], i) for i in range(n)]
pile_tops = []
piles = []
for item in items:
i = bisect.bisect_left(pile_tops, item)
if i == len(pile_tops):
pile_tops.append(item)
piles.append([item])
else:
pile_tops[i] = item
piles[i].append(item)
# k-way merge
heap = []
for pi, pile in enumerate(piles):
top = pile.pop()
heapq.heappush(heap, (top[0], top[1], pi, top))
result = []
while heap:
v, idx, pi, item = heapq.heappop(heap)
result.append(item)
if piles[pi]:
top = piles[pi].pop()
heapq.heappush(heap, (top[0], top[1], pi, top))
return [a[idx] for (_, idx) in result]7. ジョークソート
アルゴリズムの世界には、真面目な顔をしてとんでもないことを言う「ジョーク」があります。でも侮れない。これらは「ソートとは何か」という定義そのものを揺さぶるからです。
7-1. Bogosort（ボゴソート）
歴史
Bogosortは1980年代中頃、MIT・スタンフォード・カーネギーメロンなどの学生の間でジョークとして生まれました。Jargon File（ハッカー用語辞典）に「archetypically perversely awful algorithm（典型的に変態的にひどいアルゴリズム）」として記録されています。
別名：stupid sort, monkey sort, permutation sort, shotgun sort
アイデア
- 配列をランダムにシャッフル
- ソートされているか確認
- されていなければ1に戻る
トランプを空中に投げ、拾って、揃っているか確認する——揃うまで繰り返す。
import random
def bogosort(a):
"""Bogosort：運任せソート"""
a = a[:]
def is_sorted(arr):
return all(arr[i] <= arr[i+1] for i in range(len(arr)-1))
while not is_sorted(a):
random.shuffle(a)
return a計算量
- 最良：O(n)（最初から整列済み）
- 平均：O((n+1)!)
- 最悪：O(∞)（終了しない可能性）
Quantum Bogosort
理論上の冗談として「量子ボゴソート」があります：
- 量子乱数でシャッフル
- 整列していなければ宇宙を破壊
- 多世界解釈により、整列している宇宙だけが残る
計算量：O(n)（観測者から見て）
7-2. Sleep Sort（スリープソート）
歴史
2011年、4chanの/prog/板に匿名で投稿されました。天才的な発想と同時に、実用性の無さが話題に。
アイデア
各要素の値に比例した時間だけスレッドをスリープさせ、起きた順に出力。
import threading
import time
def sleep_sort(a):
"""Sleep Sort：時間を使ったソート"""
result = []
lock = threading.Lock()
def sleep_and_append(x):
time.sleep(x * 0.001) # 値に比例してスリープ
with lock:
result.append(x)
threads = [threading.Thread(target=sleep_and_append, args=(x,)) for x in a]
for t in threads:
t.start()
for t in threads:
t.join()
return result問題点
- 負の数は扱えない（負の時間スリープ不可）
- 大きな数は長時間かかる
- スレッドのオーバーヘッドで小さな値の順序が狂う
- 実時間がかかる
7-3. Stalin Sort（スターリンソート）
アイデア
「都合の悪い要素は消す」という恐ろしい発想。
配列を左から走査し、これまでの最大値より小さい要素は粛清（削除）。結果として単調増加の列が残ります。
def stalin_sort(a):
"""スターリンソート：反逆者は粛清"""
if not a:
return []
result = [a[0]]
max_val = a[0]
for x in a[1:]:
if x >= max_val:
result.append(x)
max_val = x
# else: 粛清
return result計算量
- 時間：O(n)
- 空間：O(n)（出力用）
教訓
これはソートではありません。「ソートの皮を被ったフィルタ」です。
「順序が整っている」と「データが正しい」は別物である
データ整形の現場でも、都合の悪いデータを捨てて見栄えを良くする誘惑がある。スターリンソートはその寓話です。
7-4. Abe Sort（アベソート）
アイデア
スターリンソートの亜種。削除ではなく改ざんで帳尻を合わせます。
基準より小さい値が現れたら、基準値で上書き。
def abe_sort(a):
"""Abeソート：都合の悪いデータは書き換え"""
if not a:
return []
result = a[:]
max_val = result[0]
for i in range(1, len(result)):
if result[i] < max_val:
result[i] = max_val # 改ざん
else:
max_val = result[i]
return result特徴
- 出力の長さは変わらない（スターリンソートより「ソートっぽい」）
- しかし元のデータは破壊される
教訓
「データを整形する」と「データを改ざんする」は紙一重
8. 実測ベンチマーク
以下は教育目的の参考データです。Python実装（純Python）とPython組み込み（C実装のTimsort）が混在しています。
環境: Python 3.11.2, Linux x86_64, N=5000
ランダムデータ
| 順位 | アルゴリズム | 中央値(秒) |
|---|---|---|
| 1 | python_sorted (Timsort/C) | 0.000722 |
| 2 | introsort (pure Python) | 0.005448 |
| 3 | patience_sort (pure Python) | 0.006219 |
| 4 | radix_sort_lsd (pure Python) | 0.007010 |
| 5 | quick_sort (pure Python) | 0.007072 |
| 6 | merge_sort (pure Python) | 0.012440 |
| 7 | heap_sort (pure Python) | 0.012599 |
ほぼ整列済みデータ
| 順位 | アルゴリズム | 中央値(秒) |
|---|---|---|
| 1 | python_sorted (Timsort/C) | 0.000086 |
| 2 | radix_sort_lsd (pure Python) | 0.007020 |
| 3 | patience_sort (pure Python) | 0.008095 |
| 4 | merge_sort (pure Python) | 0.008164 |
| 5 | heap_sort (pure Python) | 0.012853 |
| 6 | introsort (pure Python) | 0.019220 |
| 7 | quick_sort (pure Python) | 0.059497 |
整列済みデータ
| 順位 | アルゴリズム | 中央値(秒) |
|---|---|---|
| 1 | python_sorted (Timsort/C) | 0.000036 |
| 2 | introsort (pure Python) | 0.003949 |
| 3 | radix_sort_lsd (pure Python) | 0.007173 |
| 4 | merge_sort (pure Python) | 0.010848 |
| 5 | heap_sort (pure Python) | 0.013312 |
| 6 | patience_sort (pure Python) | 0.031808 |
| 7 | quick_sort (pure Python) | 1.246558 |
逆順データ
| 順位 | アルゴリズム | 中央値(秒) |
|---|---|---|
| 1 | python_sorted (Timsort/C) | 0.000052 |
| 2 | patience_sort (pure Python) | 0.002997 |
| 3 | radix_sort_lsd (pure Python) | 0.006854 |
| 4 | merge_sort (pure Python) | 0.007256 |
| 5 | heap_sort (pure Python) | 0.011273 |
| 6 | introsort (pure Python) | 0.012933 |
| 7 | quick_sort (pure Python) | 0.861673 |
観察
- Timsort（C実装）は圧倒的。特にほぼ整列済み・整列済みデータで真価を発揮
- クイックソートは整列済みデータで劇的に遅い（O(n²)が発生）
- 基数ソートは入力パターンに鈍感（比較しないため）
9. まとめ
アルゴリズム選択の指針
| 状況 | 推奨 |
|---|---|
| 汎用・迷ったら | 言語標準のsort（多くはTimsortかIntrosort） |
| 安定性が必要 | マージソート、Timsort |
| メモリ制約が厳しい | ヒープソート、Introsort |
| 小さい配列（N < 50） | 挿入ソート |
| 整数・値域が狭い | カウントソート、基数ソート |
| 並列化・GPU | Bitonicソート |
| ほぼ整列済み | Timsort、挿入ソート |
歴史年表
| 年 | 出来事 |
|---|---|
| 1887 | Herman Hollerithが基数ソートの原理を使ったパンチカードソーターを開発 |
| 1945 | John von Neumannがマージソートを考案（EDVAC用） |
| 1956 | Edward Harry Friendがバブルソートを論文発表 |
| 1959 | Donald Shellがシェルソートを発表 |
| 1959 | Tony Hoareがモスクワでクイックソートを発明 |
| 1964 | J.W.J. Williamsがヒープソートを発表 |
| 1968 | Ken Batcherがビットニックソートを発表 |
| 1981 | Dijkstraがスムースソートを発表 |
| 1997 | David MusserがIntrosortを発表 |
| 2002 | Tim PetersがTimsortを開発 |
最後に
ソートアルゴリズムは単なる技術ではありません。そこには70年以上の歴史があり、天才たちの閃きがあり、実務者の地道な改良があります。
「どれが一番速いか」だけでなく、「なぜそう設計されたか」「どんな問いに答えようとしたか」を理解することで、アルゴリズム的思考の本質が見えてきます。
そして、スターリンソートやボゴソートのようなジョークも、「ソートとは何か」という根本的な問いを投げかけてくれます。
データを並べ替えるという単純な問題が、これほど深い世界を持っていること——それがソートの魅力です。
10. 参考文献
公式ドキュメント・論文
- Timsort設計ノート: listsort.txt (CPython)
- Introsort論文: Musser, D.R. “Introspective Sorting and Selection Algorithms”, Software: Practice and Experience, 1997
- Quicksort原論文: Hoare, C.A.R. “Quicksort”, The Computer Journal, 1962
- Heapsort原論文: Williams, J.W.J. “Algorithm 232: Heapsort”, Communications of the ACM, 1964
- キャッシュとソート: LaMarca, A. “The Influence of Caches on the Performance of Sorting”, 1997
書籍
- Knuth, D.E. “The Art of Computer Programming, Vol.3: Sorting and Searching”
- Cormen et al. “Introduction to Algorithms”
- Sedgewick, R. “Algorithms”
Webリソース
- Wikipedia: Sorting algorithm
- Smoothsort Demystified (Keith Schwarz)
- Bitonic Sort on GPU (GPU Gems 2)
この記事がソートアルゴリズムの理解に役立てば幸いです。
コメント