ソートアルゴリズム 入門 - 計算量・安定性・実際の標準ライブラリまで

「配列を並べ替えたい」だけなら、いまはどの言語でも標準ライブラリの sort を呼べば済みます。それでもソートアルゴリズムを学ぶ価値があるのは、計算量と安定性という2つの評価軸が、ソートに限らずあらゆる場面で効いてくるからです。この記事では代表的なソートの仕組みを整理し、最後に各言語の標準ライブラリが実際に何を使っているかまで、一次情報をもとに確認します。

計算量やO記法そのものがまだあいまいな方は、先に 計算量とBig-O記法 入門 を読んでおくと、この記事の O(n log n) のような表記がすっと入ってきます。

ソートとは / なぜ学ぶか

ソートとは、要素の列をある順序（昇順・降順など）に並べ替える操作です。実務でソートアルゴリズムを自作する場面はほとんどありません。標準ライブラリが十分に速く、バグもないからです。

それでも学ぶ理由は3つあります。

• 計算量の感覚が身につく: 「二重ループで全比較すると O(n^2)」「分割統治なら O(n log n)」という肌感覚は、ソート以外のコードを書くときの見積もりにも直結します。
• 安定性の落とし穴を避けられる: 後述する「安定ソート」を理解していないと、複数キーで並べ替えたときに意図しない結果になります。
• 標準ライブラリの挙動を説明できる: なぜ最悪ケースで遅くなることがあるのか、なぜ小さい配列では別のアルゴリズムに切り替わるのか、といった疑問に答えられます。

計算量と安定性という2つの評価軸

ソートを評価するとき、まず見るのが計算量です。要素数を n として、比較や交換の回数がどう増えるかを、平均ケースと最悪ケースの両方で考えます。加えて、元の配列とは別にどれだけメモリを使うか（追加メモリ）も重要です。追加メモリが O(1) で済むソートを「in-place（その場）」と呼びます。

もう1つの軸が安定性（stability）です。安定ソートとは、同じキーを持つ要素どうしの元の並び順が、ソート後も保たれるソートのことです。

具体例で考えます。次のような「名前と得点」のリストを、得点で昇順に並べ替えるとします。

入力:  (田中, 80), (佐藤, 70), (鈴木, 80), (山田, 70)

得点だけを見ると 70, 70, 80, 80 の順ですが、同点の並びに2通りあり得ます。

• 安定ソートの結果: (佐藤, 70), (山田, 70), (田中, 80), (鈴木, 80)（元の佐藤→山田、田中→鈴木の順を維持）
• 不安定ソートの結果: 同点の内部順序は保証されない（山田→佐藤に入れ替わることもある）

これが効いてくるのが多段ソートです。先に「名前順」で並べ、次に「得点順」で並べ直すと、安定ソートなら「得点が同じなら名前順」という結果が自然に得られます。不安定ソートだと2段目で1段目の順序が壊れることがあります。データベースで ORDER BY の並びとインデックスの関係を考えるときにも通じる話で、興味があれば データベースインデックス入門 も参考になります。

基本の O(n^2) 系: バブル・選択・挿入ソート

まずは実装が単純な3つです。いずれも平均・最悪ともに O(n^2) で、大きなデータには向きませんが、仕組みの理解に最適です。

バブルソートは、隣り合う要素を比較して逆順なら交換する、を端から繰り返します。大きい要素が泡のように末尾へ浮かんでいくイメージです。実装は簡単ですが遅く、実務ではまず使いません。

選択ソートは、未整列部分から最小値を選んで先頭へ置く、を繰り返します。交換回数は最小ですが、比較回数は常に O(n^2) かかり、しかも不安定です（離れた要素を交換するため同値の順序が崩れる）。

挿入ソートは、トランプを手札に差し込むように、要素を1つずつ整列済み部分の正しい位置へ挿入します。3つの中で実務的に最も重要です。理由は、ほぼ整列済みのデータに対して O(n) に近づくこと、そして小さい配列で非常に速いことです。後述する多くの標準ライブラリは、小さな部分配列を挿入ソートで処理しています。

Pythonでの挿入ソートの実装例です。

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        # key より大きい要素を右へずらす
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a
 
print(insertion_sort([5, 2, 4, 6, 1, 3]))
# => [1, 2, 3, 4, 5, 6]

比較で「等しいときは動かさない」（a[j] > key であって以上ではない）ため、挿入ソートは安定です。

分割統治の O(n log n) 系: マージ・クイックソート

大きなデータを速く並べるには、O(n log n) 系が必要です。どちらも分割統治、つまり問題を小さく分けて解き、結果を組み合わせる戦略を取ります。

マージソートは、配列を半分ずつに分割していき、最小単位まで分けたあと、2つの整列済み列をマージ（併合）しながら組み立て直します。分割の深さが log n、各段のマージが O(n) なので、平均も最悪も安定して O(n log n) です。マージのとき「左側を優先」と決めれば安定にできます。弱点は、マージ用に O(n) の追加メモリが必要なことです。

Pythonでのマージソートの実装例です。

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[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
 
print(merge_sort([5, 2, 4, 6, 1, 3]))
# => [1, 2, 3, 4, 5, 6]

クイックソートは、ピボット（基準値）を1つ選び、それより小さい要素を左、大きい要素を右に振り分けて、両側を再帰的に並べます。追加メモリが少なく（in-placeに近く）、キャッシュ効率も良いため、平均計算量 O(n log n) の中でも定数倍が小さく、実測で非常に高速です。

ただし最悪計算量は O(n^2) です。すでにソート済みの配列で毎回端をピボットに選ぶと、分割が偏って n 段の再帰になってしまうためです。この弱点は、ピボットを工夫して緩和します。ランダムに選ぶ、先頭・中央・末尾の中央値を選ぶ（median-of-three）などの方法があり、実用実装ではさらに「偏りを検出したらヒープソートに切り替える」対策も取られます（後述のintrosort）。また素朴なクイックソートは不安定です。

ヒープソートと、比較ソートの下限

ヒープソートは、二分ヒープというデータ構造を使います。全要素をヒープに積んでから、最大値を1つずつ取り出して末尾に置いていくと、整列済みの列ができます。平均も最悪も O(n log n) で、追加メモリ O(1) の in-place という長所があります。一方でキャッシュ効率が悪く、実測ではクイックソートに負けがちで、不安定です。最悪計算量が保証される点を活かし、クイックソートの保険として組み合わせて使われます。

ここまでの6つはすべて要素どうしを比較して並べる「比較ソート」です。理論上、比較だけに頼るソートは最悪計算量 O(n log n) より速くできないことが証明されています。n 個の並び方は n! 通りあり、1回の比較で情報を高々2分割しかできないため、log2(n!) すなわち約 n log n 回の比較が最低でも必要になる、という下限です。

比較を使わないソート

キーの性質を利用すると、比較ソートの壁を越えられます。

• 計数ソート（カウントソート）: 値の種類が限られているとき、各値の出現回数を数えて並べ直します。値の範囲を k として O(n + k) で、k が小さければほぼ線形です。安定に実装できます。
• 基数ソート（radix sort）: 桁ごとに計数ソートを繰り返し、下位桁から順に安定ソートしていきます。整数や固定長文字列に有効です。
• バケツソート（bucket sort）: 値の範囲をいくつかのバケツに分け、各バケツ内を別のソートで整えてから連結します。データが一様に分布していれば高速です。

これらは万能ではなく、キーの範囲や分布に強く依存する点に注意します。範囲 k が n に比べて極端に大きいと、かえって非効率になります。

各言語の標準ライブラリは実際に何を使うか

ここが本題です。現代の標準ライブラリは、単一のアルゴリズムではなく複数を組み合わせたハイブリッドを採用しています。

• Python: list.sort と sorted はTimsortを使います。Timsortは挿入ソートとマージソートを組み合わせた適応型の安定ソートで、Tim Petersが2002年にPython向けに考案しました。すでに並んでいる「連（run）」を検出して活かすため、ほぼ整列済みのデータでは O(n) に近づきます。
• Java: Arrays.sort は対象で使い分けます。プリミティブ型の配列にはDual-Pivot Quicksort（ピボットを2つ使う版。JDK 7で導入され、小さい部分は挿入ソートに切り替え）を、オブジェクトの配列にはTimsortを使います。オブジェクトでは安定性が求められるためTimsort、プリミティブでは安定性が無意味なため高速なQuicksort、という使い分けです。
• Rust: slice::sort（安定）と slice::sort_unstable（不安定）が別々にあります。Rust 1.81（2024年）で実装が刷新され、安定版はdriftsort、不安定版はipnsortになりました。ipnsortはpdqsort（pattern-defeating quicksort）の系譜で、クイックソートの平均性能とヒープソートの最悪保証を組み合わせています。安定版のdriftsortはTimsortの系譜（glidesort由来）です。
• JavaScript: Array.prototype.sort は、ECMAScript 2019で安定ソートであることが仕様上要求されました。それ以前は不安定でも許されており、実際V8は要素数が多い配列に不安定なクイックソートを使っていました。現在のV8（Chrome 70 / V8 v7.0以降）はTimsortを採用しています。「JavaScriptのsortは不安定」という古い説明は、現在の仕様・実装では当てはまりません。
• C++: std::sort は安定性を保証せず、標準は最悪計算量 O(n log n) のみを要求します（C++11以降）。主要な実装（libstdc++など）はintrosort、すなわちクイックソートを基本に、再帰が深くなりすぎたらヒープソートへ、小さい範囲は挿入ソートへ切り替える方式です。安定なソートが必要なら std::stable_sort を使います。

共通するのは、実データはしばしば部分的に整列しているという前提を活かす設計と、小さい部分配列は挿入ソートに任せるという工夫です。

どれをいつ使うか / まとめ

主要な比較ソートを一覧にします。

実務での指針はシンプルです。

• まず標準ライブラリの sort を使う。上で見たとおり、いずれも慎重に最適化されたハイブリッドで、自作より速く安全です。
• 安定性が必要かを意識する。多段ソートをするなら安定ソートを選び、言語がそれを保証しているか確認します。Python・Javaのオブジェクト・現代JavaScript・Rustの sort は安定、Rustの sort_unstable やC++の std::sort は不安定です。
• キーの性質が特殊なら比較ソート以外も検討。値の範囲が狭い整数などなら、計数ソートや基数ソートで線形時間に近づけられます。

アルゴリズムそのものを暗記する必要はありません。大事なのは、計算量（平均と最悪）と安定性という2つの軸で道具を選べることです。この2軸は 計算量とBig-O記法 入門 で扱った考え方の応用でもあります。ソートを入り口に、計算量で物事を見積もる感覚を育てていきましょう。