配列を昇順に並べ替える。sort() を一度呼ぶだけ。あまりに当たり前で、コストなんて意識しません。

でも、コンピュータは中で何をしているのでしょうか。数字を一目で「小さい順」に並べることは、人間には簡単に見えて、機械にはできません。機械にできるのは、たった2つ。2つを比べること、そして2つを入れ替えることです。

並べ替えとは、この比較と交換を、正しい順序になるまで繰り返すことです。そして優れたアルゴリズムとは、この回数をいかに少なく済ませるかの工夫に他なりません。

▶ アニメーションで見たい方はこちら（約10分）
https://youtu.be/GGCDlEWv8XY

この記事では、比較の回数を常に意識しながら、なぜ並べ替えにコストがかかるのか、なぜ賢いやり方が桁違いに速いのかを、底から組み立てます。

バブルソート — 隣を比べて、交換するだけ

まず、最も素朴なやり方から見ていきます。隣り合う2つを比べて、左が大きければ入れ替える。これを左から右へ繰り返します。

1回左から右まで走り切ると、最大の値が、まるで泡のように右端まで押し上げられます。これがバブルソートの名前の由来です。一番大きいものが右端に確定したら、残りでもう一度。次に大きいものが、その隣に確定します。これを繰り返せば、右から順に整列が完成していきます。

def bubble_sort(arr):
    n = len(arr)
    comparisons = 0
    for i in range(n - 1):
        for j in range(n - 1 - i):
            comparisons += 1
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr, comparisons

data = [5, 3, 8, 1, 9, 2]
sorted_data, cmp = bubble_sort(data)
print(sorted_data, "比較回数:", cmp)

隣どうしを比べて交換する。たったこれだけです。仕組みは驚くほど単純です。問題は、その回数にあります。

なぜO(n²)なのか — 比較回数の正体

数えてみましょう。要素がn個あるとき、1回目のパスで比べる回数は n-1。2回目は右端が確定したので n-2。次は n-3。

これを足し合わせると、1+2+3+…という階段状の和になります。その合計は、およそ n の2乗を2で割った数（n(n-1)/2）です。

ここが本質です。要素が10倍になると、比較回数はおよそ100倍になります。これをオーダーnの2乗、O(n²) と呼びます。データが増えると、コストが爆発的に膨らみます。

なぜ2乗なのか。それは「すべての要素を、他のほぼすべての要素と比べている」からです。この無駄に気づくことが、速いアルゴリズムへの第一歩です。

選択ソートと挿入ソート — 発想を変えても2乗の壁は越えられない

別の発想もあります。未整列の中から最小値を1つ選び、先頭に置く。次は2番目に小さいものを選んで、2番目に置く。これが選択ソートです。

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # 1パスにつき交換は1回だけ
    return arr

バブルソートとの違いは、交換の回数です。バブルは何度も小刻みに入れ替えますが、選択ソートは1パスにつき交換は1回だけ。交換のコストが高い場面では有利です。

しかし、比較の回数は変わりません。最小値を見つけるには、結局すべてを見比べる必要があるからです。比較回数は、やはりn²のままです。発想を変えても、全部と全部を比べる構造が残る限り、2乗の壁は越えられません。

トランプを配られたとき、私たちは無意識に並べ替えています。新しい1枚を、すでに並んだ手札の正しい位置に差し込む。これが挿入ソートです。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 大きい要素を1つずつ右へずらす
            j -= 1
        arr[j + 1] = key
    return arr

配列の左側を「整列済み」と考え、次の1枚を取り出して、後ろから順に比べながら正しい場所まで滑り込ませます。技術的に言えば、挿入位置が見つかるまで、大きい要素を1つずつ右へずらしていく操作です。

ここで面白い性質があります。もとからほぼ整列している配列なら、ずらす回数がほとんどゼロです。挿入ソートはほぼ整列済みのデータで圧倒的に速くなる性質を持っています。この性質は、後で実用ライブラリの設計に効いてきます。

n²の壁 — 100万件で何が起きるか

ここまでの3つは、すべて比較回数がn²でした。小さなデータなら一瞬です。では、現実の規模ではどうでしょうか。

要素が100万件。n²は1兆です。1秒間に10億回比較できる速いマシンでも、およそ1000秒、17分近くかかる計算です。たった一度の並べ替えに、これだけの時間がかかります。

データは増え続けます。2乗のアルゴリズムは、ある規模を超えた瞬間に、現実的に使えなくなります。

ここで問いです。比較を「全部と全部」ではなく、もっと賢く減らす方法はないのでしょうか。答えは、問題を分割することにあります。

分割統治 — 半分に分けるという発想

大きな問題をそのまま解くのは大変です。なら、半分に割ってみましょう。

半分にした2つの山を、それぞれ並べ替える。そしてその2つを賢く合体させれば、全体が並びます。半分の山も、また半分に割る。これを繰り返すと、最後は要素1個の山になり、1個ならもう並んでいます。

ここで鍵になるのが、何回半分にできるかです。100万件は、半分にし続けると、およそ20回で1個になります。1024件なら10回です。これがlog n、対数の正体です。

全部と全部を比べるn²ではなく、n個の要素をlog n段で処理する。これがn × log n の速さを生みます。

マージソート — 分けて、併合する

分割統治を最も素直に実装したのが、マージソートです。

まず配列を、要素1個になるまで半分に割り続けます。ここでは比較も交換も起きません。ただ分けるだけです。

本番はここからの 併合（マージ） です。2つの整列済みの列を1つにまとめるとき、それぞれの先頭だけを比べて、小さい方を取り出す。これを繰り返せば、全体を1回なめるだけで合体できます。

def merge_sort(arr):
    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, 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

なぜ速いのか。各段の併合は、合わせてn個を見るだけです。そして段の数はlog n。だから全体でn × log n。100万件でも、わずか2000万回ほどの比較で済みます。2乗の1兆とは、桁が違います。

クイックソート — 基準で2つに振り分ける

もう一つの代表が、クイックソートです。発想は逆向きの分割統治です。

まず基準となる1つの要素、ピボットを選びます。そして残りを、ピボットより小さいグループと大きいグループに振り分ける。これで、ピボットは最終的な定位置に収まります。

あとは、小さいグループと大きいグループを、それぞれ同じやり方で並べ替えるだけです。再帰的に振り分けを繰り返すと、全体が並びます。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

マージソートが「分けてから併合」なら、クイックソートは「振り分けながら確定」です。追加のメモリがほとんど要らず、実測が非常に速いため、多くの言語の標準で長く使われてきました。

クイックの最悪ケース — なぜn²に戻るのか

クイックソートには弱点があります。ピボットの選び方が悪いと、速さが崩れるのです。

例えば、すでに整列済みの配列で、常に先頭をピボットに選んだらどうなるでしょうか。ピボットより小さいグループは空、大きいグループは残り全部になります。分割が、たった1つずつしか進みません。

これは、半分に割れていない、ということです。段の数がlog nではなくnになり、計算量はn²に逆戻りします。せっかくの分割統治が台無しです。

だから実用のクイックソートは、ピボットをランダムに選んだり、3つの候補の中央値を選んだりして、偏った分割を避ける工夫をしています。

計算量を一望する

ここで一度、全体を見渡しましょう。

アルゴリズム	平均計算量	最悪計算量	追加メモリ	安定性
バブルソート	O(n²)	O(n²)	O(1)	安定
選択ソート	O(n²)	O(n²)	O(1)	不安定
挿入ソート	O(n²)	O(n²)	O(1)	安定
マージソート	O(n log n)	O(n log n)	O(n)	安定
クイックソート	O(n log n)	O(n²)	O(log n)	不安定

バブル、選択、挿入はn²。マージとクイックはn × log n。最初は大差なく見えても、データが大きいほど、2乗組はみるみる引き離されていきます。

万能の最強アルゴリズムは存在しません。あるのは、状況ごとの最適だけです。

実用ライブラリの正体 — なぜTimsortなのか

では、PythonやJavaの標準ソートは、何を使っているのでしょうか。答えは、単一のアルゴリズムではありません。Timsortという、組み合わせ戦略です。

Timsortの発想はこうです。現実のデータは、完全にランダムなことは少なく、部分的に整列済みなことが多い。そこで、すでに並んでいる連続部分（ラン）を見つけ、それを土台にします。

短い部分には、ほぼ整列済みで高速な挿入ソートを使い、それらをマージソートの併合で賢くまとめます。挿入ソートの「ほぼ整列で速い」性質と、マージソートの「最悪でもn log n」の保証を、いいとこ取りしているのです。

実際、PythonとJavaはどちらもTimsortを標準ソートに採用しています（Pythonのsorted()/list.sort()、JavaのCollections.sort()が対象オブジェクト配列に対して使用）。理論の最速だけでなく、現実のデータの形に最適化する。これが実用アルゴリズムの設計思想です。

# Python の sorted() は Timsort。挙動を確認するだけなら実装は不要
data = [5, 3, 8, 1, 9, 2, 3, 3]
print(sorted(data))  # [1, 2, 3, 3, 3, 5, 8, 9]

まとめ

ソートアルゴリズムは、たくさんあるように見えて、根っこは1つでした。比較と交換を、いかに少なく済ませるか、という一点です。

全部と全部を比べる素朴なやり方はn²。問題を半分に割り続ける分割統治はn × log n。そして実用は、データの性質を突いて、理論と現実のいいとこ取りをします。

sort() という一行の裏には、こうした工夫の積み重ねがあります。次にソートを呼ぶとき、中で比較と交換ができるだけ少なく繰り返されている様子を、思い浮かべられるはずです。

チャンネル: https://www.youtube.com/@base-technology （根本解説シリーズ）