# ソートアルゴリズム：バブルソート・マージソート・クイックソートと「二乗の壁」

> バブルソートが二乗時間になる理由を転倒数で説明し、マージソートの分割統治が n log n を達成することを証明する。クイックソートの平均計算量と最悪計算量の差がピボットの選び方から生じる仕組みまで扱う。
> https://rikai.mugen-giken.com/computer-science/algorithms/sorting

## 0. この記事の要点

- バブルソートは隣り合う要素しか交換しません。1 回の交換で解消できる「順序の逆転」はちょうど 1 個なので、逆転が最悪 $n(n-1)/2$ 個ある以上、$\Theta(n^2)$ から逃げられません。遅さの原因は実装の粗さではなく、**要素を遠くへ動かせない**という設計そのものにあります。
- マージソートは配列を半分に割り、再帰的にソートしてから 2 本のソート済み列をマージします。比較回数は $n\lceil \log_2 n\rceil$ 回以下、計算時間は $\Theta(n \log n)$ です。
- クイックソートはピボットで配列を分割します。分割が均等なら $\Theta(n\log n)$ ですが、ピボットを固定位置（例えば末尾）から選ぶと、整列済みの入力で分割が毎回「$n-1$ と $0$」に偏り、$\Theta(n^2)$ に落ちます。
- ピボットを一様ランダムに選べば、期待比較回数は $2n\ln n$ 以下になります。最悪ケースは消えませんが、**入力によって決まる**のではなく**乱数によって決まる**ようになり、実用上ほぼ起こらなくなります。
- 比較だけを頼りにするソートは、どんなに工夫しても最悪 $\log_2(n!) \ge n\log_2 n - 1.443\,n$ 回の比較を必要とします。マージソートはこの下界を定数倍の意味で達成しており、その意味で「これ以上速くはならない」ところに到達しています。

## 1. 動機：二乗時間と n log n の間にある壁

ソートは、計算機が最も長い時間を費やしてきた処理のひとつです。Knuth は『The Art of Computer Programming』第 3 巻で、当時の計算機メーカーの見積もりとして、実行時間の 25% 以上がソートに使われていると紹介しています。今日でもデータベースの索引構築、外部結合、上位 $k$ 件の抽出、重複除去といった処理の中核にソートが入っています。

そして、ソートは「計算量の違いが体感できる」最初の題材でもあります。素朴に書けば $\Theta(n^2)$ になり、少し賢く書けば $\Theta(n\log n)$ になる。この差は定数倍の問題ではありません。

<Example id="ex-scale" title="100 万件を並べ替えるとき">
1 秒あたり $10^9$ 回の基本操作をこなす計算機で、$n = 10^6$ 件を並べ替えるとします。

$\Theta(n^2)$ のアルゴリズムでは、比較回数はおよそ

$$
\frac{n(n-1)}{2} = \frac{10^6 \cdot (10^6 - 1)}{2} \approx 5.0 \times 10^{11}
$$

回です。1 回の比較と付随処理を 1 操作と数えても $5.0 \times 10^{11} / 10^9 = 500$ 秒、つまり 8 分以上かかります。

$\Theta(n\log n)$ のアルゴリズムでは、$\log_2 10^6 \approx 19.9$ なので比較回数はおよそ

$$
n \log_2 n \approx 10^6 \times 19.9 = 1.99 \times 10^7
$$

回、時間にして約 $0.02$ 秒です。定数倍を無視した粗い見積もりですが、比は $500 / 0.02 = 25000$ 倍。「昼休みが終わっても終わらない処理」と「瞬時に終わる処理」の差です。しかもこの比はおよそ $(n-1)/(2\log_2 n)$ なので、$n$ を 10 倍の $10^7$ にすると $10^7/(2 \times 23.3) \approx 2.1 \times 10^5$、つまり差はさらに 8 倍以上に開きます。
</Example>

この記事では、素朴な方法がなぜ $\Theta(n^2)$ に縛られるのかを**転倒数**という量で説明し、その縛りを分割統治がどう外すのかを見ます。最後に、比較に基づく限りは $\Omega(n\log n)$ より速くできないことを証明し、マージソートが漸近的に最適であることを確かめます。計算量の記法そのものについては [計算量とO記法](/computer-science/algorithms/complexity-and-big-o)（<Ref to="computer-science/algorithms/complexity-and-big-o#def-big-o" />）を、配列・連結リスト・ヒープといった土台については [基本的なデータ構造](/computer-science/algorithms/data-structures)（<Ref to="computer-science/algorithms/data-structures#def-array" />）を前提とします。

## 2. 準備：問題の設定と評価軸

<Definition id="def-sorting-problem" title="ソート問題">
$(S, \le)$ を全順序集合とする。入力は $S$ の元からなる長さ $n$ の列 $a = (a_0, a_1, \ldots, a_{n-1})$ である。出力は $\{0, 1, \ldots, n-1\}$ 上の置換 $\pi$ であって

$$
a_{\pi(0)} \le a_{\pi(1)} \le \cdots \le a_{\pi(n-1)}
$$

を満たすもの（あるいは並べ替えた列そのもの）である。
</Definition>

全順序であることは効いています。任意の 2 元 $x, y$ について $x \le y$ か $y \le x$ の少なくとも一方が成り立つからこそ、どの 2 つを比べても必ず答えが返ります。半順序（比較不能な対がある）では、そもそも上の意味での出力が存在しないことがあります。

<Definition id="def-comparison-model" title="比較ソートモデル">
アルゴリズムが入力の要素について得られる情報が、2 要素 $a_i, a_j$ を取り出して $a_i \le a_j$ が成り立つかを問う**比較**の結果だけであるとき、そのアルゴリズムを**比較ソート**という。要素の値そのものを添字に使う、ビットを取り出すといった操作は許さない。
</Definition>

この記事で扱う 3 つはすべて比較ソートです。比較ソートに限れば <Ref to="thm-comparison-lower-bound" /> のとおり $\Omega(n\log n)$ という壁があり、計数ソートや基数ソートはこのモデルの外に出ることでその壁を回避します（<Ref to="rem-non-comparison" />）。

<Definition id="def-inversion" title="転倒（inversion）と転倒数">
列 $a = (a_0, \ldots, a_{n-1})$ に対し、添字の対 $(i, j)$ で

$$
i < j \quad \text{かつ} \quad a_i > a_j
$$

を満たすものを $a$ の**転倒**という。転倒の総数を $\operatorname{inv}(a)$ と書き、**転倒数**という。
</Definition>

転倒数は「入力がどれだけ乱れているか」の尺度です。$\operatorname{inv}(a) = 0$ は昇順に整列済みであることと同値で、要素が相異なるとき最大値は降順のときの $\binom{n}{2} = n(n-1)/2$ です。この量が、素朴なソートの遅さを説明する鍵になります。

<Definition id="def-stability" title="安定性とin-place性">
ソートアルゴリズムが**安定**であるとは、比較の意味で等しい 2 つの要素について、入力での前後関係が出力でも保たれることをいう。また、入力の配列以外に使う作業領域が $O(1)$ または $O(\log n)$ で済むとき、そのアルゴリズムを **in-place** であるという。
</Definition>

安定性は実務で効きます。「売上順に並べた表を、さらに部門順に並べ替える」とき、安定なソートを使えば同じ部門の中では売上順が保たれます。不安定なソートではこれが壊れます。

以下、配列の添字は $0$ から始め、$\lg n$ は $\log_2 n$ を表します。計算時間は「比較 1 回、代入 1 回」を単位時間として数えます（<Ref to="computer-science/algorithms/complexity-and-big-o#def-ram" text="一様コスト RAM モデル" />）。

## 3. バブルソート：隣接交換で払う代償

バブルソートは、隣り合う 2 要素の順序が逆なら入れ替える、という操作を繰り返すだけのアルゴリズムです。

```python
def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:      # 1 回も交換が起きなければ整列済み
            break
    return a
```

内側のループを 1 周すると、走査した範囲の最大値が右端まで「浮かび上がって」きます。これが名前の由来です。

<Theorem id="thm-bubble" title="バブルソートの正当性と操作回数">
長さ $n \ge 1$ の任意の列 $a$ に対して、上のアルゴリズムは次を満たす。

1. 停止し、出力は $a$ を昇順に並べ替えた列である。
2. 実行中に行われる交換の回数はちょうど $\operatorname{inv}(a)$ である。
3. 早期打ち切り（`swapped` による `break`）を行わない場合、比較回数はちょうど $n(n-1)/2$ である。早期打ち切りを行う場合でも、比較回数は $n(n-1)/2$ 以下であり、降順に並んだ入力では等号が成り立つ。
</Theorem>

<Proof of="thm-bubble">
**(1) 正当性。** まず内側ループについて、次の不変条件を示します。

> 内側ループが添字 $j$ の反復を終えた直後、$a[j+1] = \max\{a[0], \ldots, a[j+1]\}$（この時点での配列の値として）が成り立つ。

$j = 0$ のとき、比較と交換の結果 $a[1]$ には $a[0], a[1]$ の大きい方が入るので成立します。$j-1$ まで成り立つとすると、反復 $j$ の開始時点で $a[j] = \max\{a[0], \ldots, a[j]\}$ です。反復 $j$ では $a[j]$ と $a[j+1]$ を比べて大きい方を $a[j+1]$ に置くので、終了後 $a[j+1] = \max\{a[j], a[j+1]\} = \max\{a[0], \ldots, a[j+1]\}$ となります。

したがって外側ループの $i$ 回目（$i = 0, 1, \ldots$）が終わった直後には、$a[n-1-i]$ に $a[0], \ldots, a[n-1-i]$ の最大値が入ります。これを外側の不変条件

> 外側ループの反復 $i$ が終わった直後、末尾の $i+1$ 個 $a[n-1-i], \ldots, a[n-1]$ は昇順に並んでおり、かつ配列全体の中で大きい方から $i+1$ 個である

と組み合わせ、$i$ についての帰納法で示します。$i = 0$ は上の内側の結論そのものです。$i-1$ まで成り立つとすると、反復 $i$ は範囲 $a[0..n-1-i]$ のみを触り、その最大値を $a[n-1-i]$ に置きます。この最大値は「上位 $i$ 個を除いた残りの最大値」なので、全体では大きい方から $i+1$ 番目です。よって主張が従います。$i = n-2$ まで進めば末尾 $n-1$ 個が正しい位置に入り、残る $a[0]$ も自動的に最小値です。

早期打ち切りが起きた場合も正しさは保たれます。ある外側反復で 1 回も交換が起きなかったということは、その時点で $a[j] \le a[j+1]$ がすべての $j$（未確定範囲内）で成り立ち、確定済みの末尾はそれらより大きいので、配列全体が昇順だからです。

**(2) 交換回数。** 交換は「$a[j] > a[j+1]$ であるような隣接対を入れ替える」操作だけです。この操作が、配列に含まれる**要素の対**の相対順序に与える影響を考えます。入れ替えられた 2 要素 $x = a[j]$、$y = a[j+1]$（$x > y$）の対については、入れ替え前は「大きい方が先」で転倒、入れ替え後は「小さい方が先」で非転倒になります。それ以外のどの 2 要素の対についても、位置が入れ替わるのは隣接する $j, j+1$ の 2 つだけなので、前後関係は変わりません。したがって 1 回の交換で $\operatorname{inv}$ はちょうど 1 減ります。

(1) より終了時の配列は昇順、すなわち転倒数 $0$ です。転倒数は交換のたびに 1 ずつ減り、それ以外では変化しないので、交換回数は初期値 $\operatorname{inv}(a)$ に等しくなります。なお等しい要素は `a[j] > a[j+1]` が偽なので交換されず、<Ref to="def-inversion" /> の狭義不等号と整合します。

**(3) 比較回数。** 早期打ち切りをしなければ、外側の反復 $i$ で内側は $j = 0, \ldots, n-2-i$ の $n-1-i$ 回比較します。よって合計は

$$
\sum_{i=0}^{n-2} (n-1-i) = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}
$$

です。早期打ち切りは反復を減らすだけなので比較回数は増えません。降順の入力では最後の反復まで必ず交換が起きるため（各反復で少なくとも 1 つの転倒が残っている）、打ち切りは発生せず $n(n-1)/2$ 回になります。
</Proof>

<Example id="ex-bubble-trace" title="6 要素の完全なトレース">
$a = (8, 3, 5, 1, 9, 2)$ にバブルソートを適用します。各行は内側ループを 1 周した結果です。

| 周 | 比較回数 | 交換回数 | 周の終了時の配列 |
|---|---|---|---|
| 1 | 5 | 4 | $(3, 5, 1, 8, 2, 9)$ |
| 2 | 4 | 2 | $(3, 1, 5, 2, 8, 9)$ |
| 3 | 3 | 2 | $(1, 3, 2, 5, 8, 9)$ |
| 4 | 2 | 1 | $(1, 2, 3, 5, 8, 9)$ |
| 5 | 1 | 0 | $(1, 2, 3, 5, 8, 9)$（打ち切り） |

比較は合計 $5+4+3+2+1 = 15 = 6\cdot 5/2$ 回、交換は $4+2+2+1+0 = 9$ 回でした。

一方、$a$ の転倒を直接数えます。$8$ より後ろで $8$ 未満なのは $3, 5, 1, 2$ の 4 個、$3$ より後ろで $3$ 未満なのは $1, 2$ の 2 個、$5$ より後ろでは $1, 2$ の 2 個、$1$ より後ろには $1$ 未満はなく $0$ 個、$9$ より後ろでは $2$ の 1 個。合計 $4+2+2+0+1 = 9$ で、確かに交換回数と一致しています（<Ref to="thm-bubble" /> の (2)）。
</Example>

ここまでで「バブルソートは遅い」は測れましたが、まだ「なぜ遅いか」の説明にはなっていません。次の命題が答えです。

<Proposition id="prop-adjacent-lower-bound" title="隣接交換のみを使うソートの下界">
配列の要素を動かす操作として、隣接する 2 要素の交換のみを使うアルゴリズムを考える。このとき、入力 $a$ を昇順に整列するために必要な交換回数は少なくとも $\operatorname{inv}(a)$ である。とくに、要素が相異なる長さ $n$ の入力に対し、最悪の場合 $n(n-1)/2$ 回、また一様ランダムな順列に対して平均 $n(n-1)/4$ 回の交換が必要であり、どちらも $\Theta(n^2)$ である。
</Proposition>

<Proof of="prop-adjacent-lower-bound">
<Ref to="thm-bubble" /> の (2) の証明で見たとおり、隣接交換 1 回で $\operatorname{inv}$ が変化する量は $\pm 1$ です（逆順の対を入れ替えれば $-1$、順序どおりの対を入れ替えれば $+1$）。整列済みの列は $\operatorname{inv} = 0$ なので、$\operatorname{inv}(a)$ から $0$ まで 1 ステップあたり高々 1 しか減らせない以上、少なくとも $\operatorname{inv}(a)$ 回の交換が要ります。

最悪値は降順の入力で $\operatorname{inv}(a) = \binom{n}{2} = n(n-1)/2$ です。平均については <Ref to="exr-inversion-expectation" /> で $\mathbb{E}[\operatorname{inv}] = n(n-1)/4$ を示します。
</Proof>

つまりバブルソートの遅さは、実装の工夫（早期打ち切り、双方向走査など）でどうにかなるものではありません。**隣接交換という道具立て自体**が $\Theta(n^2)$ を要求しています。速くするには、1 回の操作で多数の転倒をまとめて解消できるように、要素を遠くへ動かす仕組みが必要です。これが次節以降の共通するアイデアです。

<Remark id="rem-insertion-sort">
同じ $\Theta(n^2)$ でも、挿入ソートの実行時間は $\Theta(n + \operatorname{inv}(a))$ になり（比較回数の数え上げは <Ref to="computer-science/algorithms/complexity-and-big-o#ex-insertion-sort" />）、ほとんど整列済みの入力（$\operatorname{inv}(a) = O(n)$）では線形時間で終わります。バブルソートは早期打ち切りを入れても外側ループが「最も左へ動くべき要素の移動距離」に比例して回るため、この性質を持ちません。小さい配列や「ほぼ整列済み」の配列に対しては、実務では挿入ソートが選ばれます。
</Remark>

## 4. マージソート：分割統治が壁を破る

**分割統治法**（divide and conquer）は、問題を同種の小さい問題に分割し、再帰的に解き、その解を統合する設計方針です。3 つの段階に名前が付いています。

- **分割（Divide）**：問題を小さな部分問題に分ける。
- **統治（Conquer）**：部分問題を再帰的に解く。十分小さければ直接解く。
- **統合（Combine）**：部分解を合わせて元の問題の解を作る。

ソートに当てはめると、「配列を前半と後半に分け、それぞれをソートし、2 本のソート済み列をマージする」となります。これがマージソートです。

<Figure caption="マージソートの分割の様子。分割は配列を半分にするだけで、比較は 1 回も行いません。仕事はすべて、葉から根へ戻るときのマージで行われます。">
<Mermaid code={`flowchart TB
  A["8 3 5 1 9 2"] --> B["8 3 5"]
  A --> C["1 9 2"]
  B --> D["8"]
  B --> E["3 5"]
  C --> F["1"]
  C --> G["9 2"]
  E --> H["3"]
  E --> I["5"]
  G --> J["9"]
  G --> K["2"]`} />
</Figure>

```python
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 merge_sort(a):
    if len(a) <= 1:
        return a[:]
    m = len(a) // 2
    return merge(merge_sort(a[:m]), merge_sort(a[m:]))
```

<Lemma id="lem-merge" title="マージの正当性とコスト">
`left` が長さ $p$ の昇順列、`right` が長さ $q$ の昇順列であるとき、上の `merge` は次を満たす。

1. 出力は `left` と `right` の全要素からなる長さ $p+q$ の昇順列である。
2. 比較回数は高々 $p + q - 1$ 回であり、実行時間は $\Theta(p+q)$ である。
3. `left` と `right` の中に比較の意味で等しい要素があるとき、`left` 側の要素が先に出力される。
</Lemma>

<Proof of="lem-merge">
**(1)** `while` ループについて、次の不変条件が保たれることを示します。

> `result` は昇順であり、その各要素は `left[i:]` と `right[j:]` のどの要素以下である。また `result` は `left[:i]` と `right[:j]` を合わせたものと一致する。

初期状態では $i = j = 0$ かつ `result` が空なので、「各要素は〜以下」という条件は要素が 1 つもないため空虚に成り立ち、`left[:0]` と `right[:0]` もともに空です。反復の各回で、`left[i] <= right[j]` のときに `left[i]` を追加する場合を考えます。`left` は昇順なので `left[i]` は `left[i:]` の最小値、条件より `right[j]` 以下で、`right` も昇順だから `right[j:]` のすべて以下です。すなわち `left[i]` は残っている全要素の最小値なので、追加後も「`result` の各要素は残りのどの要素以下」が保たれ、`result` は昇順のままです。`else` の場合（`left[i] > right[j]`）も同様に `right[j]` が残りの最小値です。

ループ終了時、`left` か `right` の一方は消費し尽くされています。残った側は昇順で、しかも不変条件より `result` のどの要素以上なので、そのまま連結すれば全体が昇順になります。要素の個数と多重度も保たれます。ループ内では消費した要素をそのまま 1 個ずつ `result` に追加し、最後に未消費の残りを順に連結するだけで、削除も複製も行っていないからです。

**(2)** `while` ループの 1 反復につき比較は 1 回で、そのたびに `result` の長さが 1 増えます。ループは `left` か `right` の一方が尽きた時点で止まるので、反復回数は高々 $p+q-1$ 回です（最後の 1 要素は必ず連結側に回るため）。残りの連結と合わせて、操作回数は $p+q$ に比例します。

**(3)** 等しい要素については `left[i] <= right[j]` が真になり、`left` 側が先に出力されます。
</Proof>

<Theorem id="thm-mergesort" title="マージソートの正当性と計算量">
長さ $n \ge 1$ の任意の入力に対して `merge_sort` は停止し、昇順に整列した列を返す。さらに、比較回数 $C(n)$ と実行時間 $T(n)$ は

$$
C(n) \le n \lceil \log_2 n \rceil, \qquad T(n) = O(n\log n)
$$

を満たす。またこのアルゴリズムは <Ref to="def-stability" /> の意味で安定である。
</Theorem>

<Proof of="thm-mergesort">
**正当性と停止性。** 入力長 $n$ についての強い帰納法によります。$n \le 1$ なら入力はそのまま昇順で、複製を返して停止します。$n \ge 2$ のとき、$m = \lfloor n/2 \rfloor$ とすると $1 \le m < n$ かつ $1 \le n - m < n$ なので、2 つの再帰呼び出しは帰納法の仮定によりそれぞれ停止して昇順列を返します。あとは <Ref to="lem-merge" /> の (1) から、`merge` の出力が全体の昇順列になります。安定性は <Ref to="lem-merge" /> の (3) と、前半が常に `left` 側に来ることから、同じく帰納法で従います。

**比較回数。** $h(n) = \lceil \log_2 n \rceil$ と書きます。<Ref to="lem-merge" /> の (2) より

$$
C(1) = 0, \qquad C(n) \le C(\lceil n/2 \rceil) + C(\lfloor n/2 \rfloor) + (n-1) \quad (n \ge 2)
$$

が成り立ちます（`merge_sort` は $m = \lfloor n/2 \rfloor$ で切るので部分の長さは $\lfloor n/2 \rfloor$ と $\lceil n/2 \rceil$ です）。

まず補助的な不等式を示します。$n \ge 2$、$k = h(n)$ とすると $k \ge 1$ かつ $2^{k-1} < n \le 2^k$ です。両辺を 2 で割って天井を取ると $\lceil n/2 \rceil \le \lceil 2^k / 2 \rceil = 2^{k-1}$ なので $h(\lceil n/2 \rceil) \le k - 1$、さらに $h$ は単調非減少で $\lfloor n/2 \rfloor \le \lceil n/2 \rceil$ だから $h(\lfloor n/2 \rfloor) \le k-1$ も従います。

これを使って $C(n) \le n\,h(n)$ を $n$ についての強い帰納法で示します。$n = 1$ では $C(1) = 0 = 1 \cdot h(1)$ で成立。$n \ge 2$ とし、$n$ より小さいすべてで成立を仮定します。$a = \lceil n/2 \rceil$、$b = \lfloor n/2 \rfloor$ と置くと $a + b = n$、$a, b < n$ なので

$$
\begin{aligned}
C(n) &\le a\,h(a) + b\,h(b) + (n-1) \\
&\le a\,(h(n)-1) + b\,(h(n)-1) + (n-1) \\
&= n\,h(n) - n + n - 1 = n\,h(n) - 1 \le n\,h(n)
\end{aligned}
$$

となり、主張が示されました。

**実行時間。** マージ以外の処理（部分列の切り出しと再帰呼び出しの管理）も長さに比例するので、ある定数 $c > 0$ が存在して

$$
T(1) \le c, \qquad T(n) \le T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + c\,n
$$

とできます。$T(n) \le c\,n\,(h(n)+1)$ を同じ帰納法で示します。$n=1$ では $T(1) \le c = c \cdot 1 \cdot (0+1)$。$n \ge 2$ では、上と同じ $a, b$ を使って

$$
\begin{aligned}
T(n) &\le c\,a\,(h(a)+1) + c\,b\,(h(b)+1) + c\,n \\
&\le c\,a\,h(n) + c\,b\,h(n) + c\,n = c\,n\,(h(n)+1)
\end{aligned}
$$

です（2 行目で $h(a)+1 \le h(n)$、$h(b)+1 \le h(n)$ を使いました）。$h(n) < \log_2 n + 1$ なので $T(n) = O(n \log n)$ を得ます。
</Proof>

この証明の中身を絵にすると、次のようになります。再帰の各段では、部分配列の長さの合計が常に $n$ です。マージのコストは長さに比例するので、**どの段でも合計コストは $cn$**。段数が $\lceil \log_2 n\rceil + 1$ なので、全体が $cn\log n$ の程度になります。分割統治の計算量がこの形になる理由は、ほとんどこの一枚に尽きています。

<Figure caption="マージソートの再帰木。各段で部分配列の長さの合計は n、したがってマージの合計コストも各段で cn。段数がおよそ log₂ n + 1 なので全体は cn log₂ n の程度になります。">
<svg viewBox="0 0 680 250" width="100%" role="img" aria-label="マージソートの再帰木において各段のコストが cn になることを示す図">
  <g fill="none" stroke="currentColor" stroke-width="1.5">
    <rect x="30" y="16" width="460" height="30" rx="4" />
    <rect x="30" y="76" width="225" height="30" rx="4" />
    <rect x="265" y="76" width="225" height="30" rx="4" />
    <rect x="30" y="136" width="107" height="30" rx="4" />
    <rect x="148" y="136" width="107" height="30" rx="4" />
    <rect x="265" y="136" width="107" height="30" rx="4" />
    <rect x="383" y="136" width="107" height="30" rx="4" />
  </g>
  <g stroke="currentColor" stroke-width="1" opacity="0.55">
    <line x1="260" y1="46" x2="142" y2="76" />
    <line x1="260" y1="46" x2="377" y2="76" />
    <line x1="142" y1="106" x2="83" y2="136" />
    <line x1="142" y1="106" x2="201" y2="136" />
    <line x1="377" y1="106" x2="318" y2="136" />
    <line x1="377" y1="106" x2="436" y2="136" />
  </g>
  <g fill="currentColor" font-size="14" text-anchor="middle">
    <text x="260" y="36">長さ n</text>
    <text x="142" y="96">n/2</text>
    <text x="377" y="96">n/2</text>
    <text x="83" y="156">n/4</text>
    <text x="201" y="156">n/4</text>
    <text x="318" y="156">n/4</text>
    <text x="436" y="156">n/4</text>
    <text x="260" y="192">…（長さ 1 になるまで分割が続く）…</text>
  </g>
  <g fill="var(--sl-color-accent)" font-size="14" text-anchor="start">
    <text x="510" y="36">この段の合計 cn</text>
    <text x="510" y="96">この段の合計 cn</text>
    <text x="510" y="156">この段の合計 cn</text>
    <text x="510" y="192">…</text>
  </g>
  <g fill="currentColor" font-size="13" text-anchor="middle">
    <text x="300" y="228">段数はおよそ log₂ n + 1 、よって総コストはおよそ cn log₂ n</text>
  </g>
</svg>
</Figure>

<Example id="ex-merge-trace" title="マージの回数を数え切る">
<Ref to="ex-bubble-trace" /> と同じ $a = (8, 3, 5, 1, 9, 2)$ をマージソートします。分割は上の図のとおりです。葉から順にマージしていきます。

| マージ | 入力 | 出力 | 比較回数 |
|---|---|---|---|
| 1 | $(3)$, $(5)$ | $(3,5)$ | 1 |
| 2 | $(8)$, $(3,5)$ | $(3,5,8)$ | 2 |
| 3 | $(9)$, $(2)$ | $(2,9)$ | 1 |
| 4 | $(1)$, $(2,9)$ | $(1,2,9)$ | 1 |
| 5 | $(3,5,8)$, $(1,2,9)$ | $(1,2,3,5,8,9)$ | 5 |

マージ 2 を細かく見ます。`left` $=(8)$、`right` $=(3,5)$。$8 \le 3$ は偽なので $3$ を出力、$8 \le 5$ も偽なので $5$ を出力、ここで `right` が尽きたので残った $8$ を連結して $(3,5,8)$。比較 2 回です。マージ 5 では $3$ と $1$、$3$ と $2$、$3$ と $9$、$5$ と $9$、$8$ と $9$ の 5 回を比較し、`left` が尽きた時点で残りの $9$ を連結します。

合計比較回数は $1+2+1+1+5 = 10$ 回。<Ref to="thm-mergesort" /> の上界 $n\lceil \log_2 n\rceil = 6 \times 3 = 18$ を確かに下回っています。同じ入力に対してバブルソートは比較 15 回・交換 9 回でした（<Ref to="ex-bubble-trace" />）。$n=6$ でも既に差が出ています。

なお、マージ 5 で $3$ を出力する直前までに出力された $1, 2$ は、$(8,3,5)$ 側の 3 要素すべてを一気に追い越しています。1 回の操作で複数の転倒がまとめて解消される、これが <Ref to="prop-adjacent-lower-bound" /> の縛りを外している場所です。
</Example>

<Remark id="rem-mergesort-space">
マージソートの弱点は作業領域です。上の実装は再帰のたびに新しいリストを作るので $\Theta(n)$ の追加メモリを使い、<Ref to="def-stability" /> の意味で in-place ではありません。作業配列を 1 本だけ確保して使い回す実装でも $\Theta(n)$ です。一方で、連結リストに対しては追加の配列なしにポインタの付け替えだけでマージできるため、外部記憶やリスト構造のソートではマージソートが第一候補になります。データ構造ごとの得失は [基本的なデータ構造](/computer-science/algorithms/data-structures) を、連結リストの操作コストは <Ref to="computer-science/algorithms/data-structures#prop-list" /> を参照してください。
</Remark>

## 5. クイックソート：平均は速く、最悪は遅い

マージソートは「分けるのは楽、合わせるのが仕事」でした。クイックソートはこれを逆にします。**分けるときに仕事をして、合わせるときは何もしない**。C. A. R. Hoare が 1959 年に考案したこのアルゴリズムは、基準値（ピボット）より小さい要素を左に、大きい要素を右に集める操作を再帰的に繰り返します。分割が終わればピボットは最終位置に確定し、左右をそれぞれソートすれば、連結するだけで全体が整列します。

ここでは実装が単純な Lomuto の分割法を使います。

```python
def partition(a, lo, hi):
    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]     # ピボットを境界へ
    return i


def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)
        quick_sort(a, lo, p - 1)
        quick_sort(a, p + 1, hi)
    return a
```

<Lemma id="lem-partition" title="Lomuto 分割の正当性">
$lo \le hi$ とし、`partition(a, lo, hi)` を呼ぶ。返り値を $p$、呼び出し前の `a[hi]` の値を $v$ とすると、呼び出し後には

$$
lo \le p \le hi, \quad a[p] = v, \quad a[k] \le v \ (lo \le k < p), \quad a[k] > v \ (p < k \le hi)
$$

が成り立ち、部分配列 $a[lo..hi]$ の要素の多重集合は変化しない。比較回数はちょうど $hi - lo$ 回である。
</Lemma>

<Proof of="lem-partition">
`for` ループについて、反復 $j$ の開始時点で次の不変条件が成り立つことを $j$ についての帰納法で示します。

$$
a[k] \le v \ (lo \le k < i), \qquad a[k] > v \ (i \le k < j)
$$

$j = lo$ のときは $i = lo$ で、2 つの範囲がともに空なので成立します。反復 $j$ では 2 つの場合があります。$a[j] > v$ のときは何もしないので、$i \le k < j+1$ の範囲に $a[j] > v$ が加わるだけで不変条件は保たれます。$a[j] \le v$ のときは $a[i]$ と $a[j]$ を交換します。不変条件より交換前の $a[i]$ は（$i < j$ なら）$v$ より大きく、交換後は位置 $j$ に移るので「$v$ より大きい領域」の右端に収まります。一方 $a[j] \le v$ は位置 $i$ に移り、その後 $i$ が 1 増えるので「$v$ 以下の領域」に含まれます。$i = j$ の場合は自分自身との交換で、やはり成立します。

ループ終了時（$j = hi$）には $a[k] \le v$（$lo \le k < i$）と $a[k] > v$（$i \le k < hi$）が成り立ちます。最後に $a[i]$ と $a[hi] = v$ を交換すると、$v$ が位置 $i$ に来て、それまで $a[i]$ にあった（$v$ より大きい）値は末尾に移ります。よって $p = i$ として主張の形になります。$lo \le i \le hi$ は $i$ が $lo$ から始まり高々 $hi - lo$ 回増えることから従います。要素の多重集合が変わらないのは、操作が交換だけだからです。比較 `a[j] <= pivot` は $j = lo, \ldots, hi-1$ の各回でちょうど 1 回なので $hi - lo$ 回です。
</Proof>

<Ref to="lem-partition" /> により、`quick_sort` の正当性は入力長についての強い帰納法で従います。$p$ が確定位置なので、$a[lo..p-1]$ と $a[p+1..hi]$ をそれぞれ整列すれば全体が整列し、部分配列の長さはどちらも元より真に小さいからです。統合の手間はゼロで、マージに相当する処理がありません。

### 5.1. 最悪計算量

<Theorem id="thm-quicksort-worst" title="決定的クイックソートの最悪計算量">
相異なる $n$ 個の要素からなる任意の入力に対し、上の `quick_sort` の比較回数は高々 $n(n-1)/2$ 回である。さらに、入力が既に昇順に整列されている場合、比較回数はちょうど $n(n-1)/2$ 回であり、再帰の深さは $n$ に達する。したがって最悪計算量は $\Theta(n^2)$ である。
</Theorem>

<Proof of="thm-quicksort-worst">
**上界。** 比較は `a[j] <= pivot` の形でしか起こらないので、比較される 2 要素の一方は必ずその呼び出しのピボットです。<Ref to="lem-partition" /> より、ピボットは確定位置 $p$ に置かれ、その後の再帰呼び出し `quick_sort(a, lo, p-1)` と `quick_sort(a, p+1, hi)` はどちらも位置 $p$ を含みません。つまりピボットは以後の部分配列に二度と現れないので、ある 2 要素の対が比較されるのは高々 1 回です。対の総数は $\binom{n}{2} = n(n-1)/2$ なので、比較回数はこれ以下です。

**昇順入力での等号。** 長さ $m$ の昇順部分配列に対して `partition` を呼ぶと、ピボット `a[hi]` はその部分配列の最大値です。よってループ中つねに `a[j] <= pivot` が成り立ち、$i$ は毎回増えて最終的に $i = hi$、返り値は $p = hi$ です。交換もすべて自分自身との交換なので配列は昇順のまま保たれます。したがって再帰は「長さ $m-1$」と「長さ $0$」に分かれ、比較は <Ref to="lem-partition" /> より $m-1$ 回。これを $m = n, n-1, \ldots, 2$ と繰り返すので、比較回数の合計は

$$
(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}
$$

となり、再帰の深さは $n$ です。比較 1 回あたりの手間は定数なので、実行時間も $\Theta(n^2)$ です。
</Proof>

<Example id="ex-quicksort-sorted" title="最も苦手な入力">
$a = (1,2,3,4,5)$ に `quick_sort` を適用します。

1. `partition(a, 0, 4)`：ピボット $=5$。$1,2,3,4$ はすべて $5$ 以下なので $i$ は $0 \to 4$ と進み、最後に `a[4]` と `a[4]` を交換して $p=4$。比較 4 回。左は $a[0..3]$、右は空。
2. `partition(a, 0, 3)`：ピボット $=4$。同様に $p=3$。比較 3 回。
3. `partition(a, 0, 2)`：ピボット $=3$、$p=2$。比較 2 回。
4. `partition(a, 0, 1)`：ピボット $=2$、$p=1$。比較 1 回。

合計 $4+3+2+1 = 10 = 5\cdot 4/2$ 回。$n=10^6$ の整列済みデータなら比較は $5\times 10^{11}$ 回、そのうえ再帰の深さが $10^6$ になるので、多くの処理系ではスタックが先に溢れます。「既にソートされたデータを再度ソートしたら固まった」という現象の正体がこれです。
</Example>

<Remark id="rem-duplicates">
もうひとつの落とし穴が重複です。全要素が等しい配列に Lomuto 分割を適用すると、`a[j] <= pivot` が常に真なので $p = hi$ となり、やはり「$n-1$ と $0$」の分割になって $\Theta(n^2)$ です。この対策には、ピボットと等しい要素をまとめて中央に置く 3 分割（Dutch national flag 型）が使われます。Bentley と McIlroy の "Engineering a Sort Function" は、この種の実装上の罠を体系的に扱った古典です。
</Remark>

### 5.2. 平均計算量

最悪ケースが $\Theta(n^2)$ でもクイックソートが実用され続けているのは、平均が速く、しかもその「平均」を乱数で保証できるからです。ピボットを部分配列から一様ランダムに選ぶ版を**ランダム化クイックソート**と呼びます（`pivot = a[hi]` の代わりに、`lo` 以上 `hi` 以下の添字を一様に選んで `a[hi]` と交換してから同じ処理をします）。

<Theorem id="thm-quicksort-average" title="ランダム化クイックソートの期待比較回数">
相異なる $n$ 個の要素からなる任意の入力に対し、各再帰呼び出しでピボットをその部分配列から一様ランダムに（過去の選択と独立に）選ぶクイックソートの期待比較回数 $\mathbb{E}[C_n]$ は

$$
\mathbb{E}[C_n] \;=\; \sum_{1 \le i < j \le n} \frac{2}{\,j-i+1\,} \;<\; 2n\,(H_n - 1) \;\le\; 2n \ln n
$$

を満たす。ここで $H_n = \sum_{k=1}^{n} 1/k$ は調和数である。とくに期待実行時間は $O(n\log n)$ である。
</Theorem>

<Proof of="thm-quicksort-average">
入力を昇順に並べたものを $z_1 < z_2 < \cdots < z_n$ とし、$i < j$ に対して $Z_{ij} = \{z_i, z_{i+1}, \ldots, z_j\}$ と置きます。確率変数

$$
X_{ij} = \begin{cases} 1 & \text{実行中に } z_i \text{ と } z_j \text{ が比較される} \\ 0 & \text{そうでない} \end{cases}
$$

を導入します。<Ref to="thm-quicksort-worst" /> の証明で見たように、どの対も高々 1 回しか比較されないので、比較回数の総数は $C_n = \sum_{i<j} X_{ij}$ と書けます。期待値の線形性より $\mathbb{E}[C_n] = \sum_{i<j} \Pr[X_{ij} = 1]$ です。

**主張：$z_i$ と $z_j$ が比較されるのは、$Z_{ij}$ の中で最初にピボットに選ばれた元が $z_i$ または $z_j$ であるとき、かつそのときに限る。**

まず、$Z_{ij}$ の元がすべて同じ部分配列に入っている限り、$z_i$ と $z_j$ は比較されていません。比較は必ずピボットとの間で起こるので、$Z_{ij}$ からまだ 1 つもピボットが選ばれていない以上、$z_i$ と $z_j$ が比較されることはないからです。またこの間、ピボット $p$ が $Z_{ij}$ の外から選ばれても $Z_{ij}$ は分かれません。実際 $p \notin Z_{ij}$ なら $p < z_i$ か $p > z_j$ のいずれかで（$Z_{ij}$ は値の順序で連続した区間だからです）、前者なら <Ref to="lem-partition" /> により $Z_{ij}$ の元はすべて右側へ、後者ならすべて左側へ入ります。

そこで、$Z_{ij}$ から初めてピボットに選ばれた元を $p^{*}$ とします。この時点で $Z_{ij}$ は同じ部分配列にあります。$p^{*} = z_i$ または $p^{*} = z_j$ なら、ピボットは同じ部分配列の全要素と比較されるので、$z_i$ と $z_j$ は比較されます。$z_i < p^{*} < z_j$ なら、<Ref to="lem-partition" /> により $z_i$ は左側、$z_j$ は右側に入り、以後同じ部分配列に同居しないので二度と比較されません。主張が示されました。

**確率の計算。** $Z_{ij}$ を含む部分配列からピボットが一様ランダムに選ばれるとき、選ばれた元が $Z_{ij}$ に属するという条件の下では、$Z_{ij}$ の各元が等確率です。$Z_{ij}$ の外が選ばれた場合は上で見たとおり $Z_{ij}$ はそのまま次の部分配列へ持ち越されるので、同じ議論が繰り返されます。したがって「$Z_{ij}$ の中で最初にピボットになる元」は $Z_{ij}$ 上の一様分布に従い、それが $z_i$ か $z_j$ である確率は

$$
\Pr[X_{ij} = 1] = \frac{2}{|Z_{ij}|} = \frac{2}{j-i+1}
$$

です。

**和の評価。** $d = j - i$ と置いて数え上げます。

$$
\begin{aligned}
\mathbb{E}[C_n] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j-i+1}
= \sum_{i=1}^{n-1} \sum_{d=1}^{n-i} \frac{2}{d+1}
= \sum_{i=1}^{n-1} 2\left(H_{n-i+1} - 1\right)
\le 2(n-1)(H_n - 1)
\end{aligned}
$$

最後に $H_n - 1 \le \ln n$ を使います。これは $k \ge 2$ に対し $1/k \le \int_{k-1}^{k} dx/x$ が成り立つ（区間 $[k-1,k]$ 上で $1/x \ge 1/k$）ことから

$$
H_n - 1 = \sum_{k=2}^{n} \frac{1}{k} \le \int_{1}^{n} \frac{dx}{x} = \ln n
$$

と従います。以上より $\mathbb{E}[C_n] < 2n(H_n-1) \le 2n\ln n$ です。比較以外の処理（交換と添字操作）は比較回数に比例するので、期待実行時間は $O(n\log n)$ です。
</Proof>

$2n\ln n = 2\ln 2 \cdot n\log_2 n \approx 1.386\, n \log_2 n$ ですから、ランダム化クイックソートの比較回数は平均でマージソートの上界のおよそ 1.4 倍です。それでも実測でクイックソートが速いことが多いのは、追加メモリを使わず配列を直接書き換えるためキャッシュ効率がよく、内側ループが「比較・条件付き交換・添字加算」だけで済むからです。計算量が同じ $\Theta(n\log n)$ でも定数倍が違う、という典型例になっています。

<Remark id="rem-pivot-strategies">
最悪ケースへの対策は、突き詰めると「ピボットの選び方」です。

- **ランダム選択**：<Ref to="thm-quicksort-average" /> の設定です。最悪ケースは消えませんが、その発生確率は入力ではなく乱数に依存します。特定の入力を狙って遅くさせることが（乱数列を知らない限り）できなくなる点も実用上重要です。
- **median-of-three**：先頭・中央・末尾の 3 つの中央値をピボットにします。整列済み入力に対して中央付近が選ばれるため <Ref to="ex-quicksort-sorted" /> の破綻を防げます。ただし、この規則を知ったうえで作られた敵対的入力では依然として $\Theta(n^2)$ になります。
- **イントロソート**：再帰の深さが $2\lfloor \log_2 n \rfloor$ を超えたらヒープソートに切り替えます。ヒープソートは最悪 $O(n\log n)$ なので、全体として最悪 $O(n\log n)$ を保証しつつ、通常はクイックソートの速さで動きます。C++ の標準ライブラリの `std::sort` が採用している方式です。
</Remark>

## 6. 比較ソートの限界

ここまでで $\Theta(n\log n)$ のアルゴリズムを 2 つ得ました。では、もっと速い比較ソートはあるのでしょうか。答えは「ない」です。しかも、個々のアルゴリズムを調べるのではなく、**あらゆる比較ソートを一度に**扱って証明できます。

考え方はこうです。比較ソートは、入力の要素を直接見ることができず、比較の答え（真か偽か）だけを頼りに動きます。したがって、相異なる $n$ 個の要素に対する実行の様子は、内部節点が「$a_i \le a_j$ か」という質問、枝が答え、葉が出力する並べ替えに対応する二分木（**決定木**）で表せます。1 回の比較で得られる情報は 1 ビット、$h$ 回の比較で区別できる結果は高々 $2^h$ 通りです。一方、正しくソートするには $n!$ 通りの並べ替えをすべて区別できなければなりません。

<Theorem id="thm-comparison-lower-bound" title="比較ソートの下界">
相異なる $n$ 個の要素を正しく整列する任意の決定的比較ソートについて、最悪の場合に必要な比較回数 $h(n)$ は

$$
h(n) \ge \log_2 (n!) \ge n \log_2 n - n \log_2 e > n\log_2 n - 1.443\,n
$$

を満たす。とくに $h(n) = \Omega(n\log n)$ である。
</Theorem>

<Proof of="thm-comparison-lower-bound">
アルゴリズムを固定し、要素数 $n$ の相異なる入力に対する決定木を考えます。入力の並べ替え方は $n!$ 通りあり、それぞれに対して出力すべき置換は異なります。もし 2 つの異なる並べ替え $\sigma \ne \tau$ が決定木の同じ葉に到達するなら、アルゴリズムは両者に同じ出力を返すことになり、少なくとも一方では誤った結果になります。よって決定木の葉は少なくとも $n!$ 個あります。

高さ $h$ の二分木の葉の個数は高々 $2^h$ 個です（高さ $h$ についての帰納法：$h=0$ なら葉は 1 個。高さ $h$ の木は、根の 2 つの部分木がそれぞれ高さ $h-1$ 以下なので、葉は高々 $2 \cdot 2^{h-1} = 2^h$ 個）。最悪の場合の比較回数は決定木の高さ $h$ に等しいので、$2^{h} \ge n!$、すなわち $h \ge \log_2 (n!)$ を得ます。

次に $n! \ge (n/e)^n$ を示します。指数関数の級数展開

$$
e^{n} = \sum_{k=0}^{\infty} \frac{n^k}{k!} \ge \frac{n^n}{n!}
$$

（右辺は $k = n$ の項だけを残したもので、他の項はすべて非負）から $n! \ge n^n / e^n = (n/e)^n$ が従います。両辺の $\log_2$ を取ると

$$
\log_2 (n!) \ge n \log_2 \frac{n}{e} = n\log_2 n - n\log_2 e
$$

で、$\log_2 e = 1.4426\ldots < 1.443$ です。
</Proof>

<Corollary id="cor-mergesort-optimal" title="マージソートの漸近的最適性">
マージソートの最悪比較回数は $n\lceil \log_2 n\rceil$ 以下であり、任意の比較ソートの最悪比較回数の下界 $n\log_2 n - 1.443n$ と比べて、比が $n \to \infty$ で $1$ に収束する。すなわちマージソートは比較ソートの中で漸近的に最適であり、その最悪計算量は $\Theta(n\log n)$ である。
</Corollary>

<Proof of="cor-mergesort-optimal">
上界は <Ref to="thm-mergesort" />、下界は <Ref to="thm-comparison-lower-bound" /> です。以下 $n \ge 3$ とします（このとき $\log_2 n \ge 1.584 > 1.443$ なので下界は正です）。$\lceil \log_2 n \rceil < \log_2 n + 1$ と、上界が下界以上であることから、比較回数の比は

$$
1 \le \frac{n\lceil \log_2 n\rceil}{\,n\log_2 n - 1.443n\,} < \frac{\log_2 n + 1}{\log_2 n - 1.443} \longrightarrow 1 \quad (n \to \infty)
$$

です（右端の極限は、分母・分子を $\log_2 n$ で割れば $(1 + 1/\log_2 n)/(1 - 1.443/\log_2 n) \to 1$ から従います）。実行時間についても、上界 $O(n\log n)$ は <Ref to="thm-mergesort" />、下界は比較 1 回に少なくとも定数時間かかることと <Ref to="thm-comparison-lower-bound" /> から $\Omega(n\log n)$ となり、あわせて $\Theta(n\log n)$ です。
</Proof>

<Remark id="rem-non-comparison">
この下界は「比較しか使えない」という制約から来ています。制約を外せば破れます。たとえば入力が $0$ 以上 $K$ 未満の整数であることが分かっているなら、各値の出現回数を数える計数ソートが $\Theta(n + K)$ で動きます。$d$ 桁の整数を下位桁から安定ソートしていく基数ソートは $\Theta(d(n+K))$ です。これらは要素の値を配列の添字として使っており、<Ref to="def-comparison-model" /> の外にあるので <Ref to="thm-comparison-lower-bound" /> の適用対象ではありません。下界の主張は、必ず「どの計算モデルでの下界か」とセットで読む必要があります。
</Remark>

<Aside type="note">
<Ref to="thm-comparison-lower-bound" /> のように、**あらゆるアルゴリズムに対する下界**が証明できる例は実は多くありません。比較モデルという強い制約があるからこそ、情報量の議論が通りました。制約のない一般の計算モデルで「この問題を解くには最低これだけかかる」を示すのは極めて難しく、その難しさの象徴が [P≠NP予想](/computer-science/algorithms/p-vs-np) です。上界（速いアルゴリズムの提示）と下界（不可能性の証明）は、難易度がまったく違う営みです。
</Aside>

## 7. 使い分け

3 つ（と比較用にヒープソート）をまとめます。$n$ は要素数、追加メモリは入力配列以外に必要な作業領域です。

| アルゴリズム | 最悪時間 | 平均時間 | 追加メモリ | 安定性 | 特徴 |
|---|---|---|---|---|---|
| バブルソート | $\Theta(n^2)$ | $\Theta(n^2)$ | $O(1)$ | 安定 | 実用価値はほぼない。転倒数の教材として有用 |
| 挿入ソート | $\Theta(n^2)$ | $\Theta(n^2)$ | $O(1)$ | 安定 | $\Theta(n + \operatorname{inv})$ なので小規模・ほぼ整列済みに強い |
| マージソート | $\Theta(n\log n)$ | $\Theta(n\log n)$ | $\Theta(n)$ | 安定 | 最悪保証あり。外部ソート・連結リスト向き |
| クイックソート | $\Theta(n^2)$ | $\Theta(n\log n)$ | $O(\log n)$ | 不安定 | 定数倍が小さく実測が速い。ピボット対策が必須 |
| ヒープソート | $\Theta(n\log n)$ | $\Theta(n\log n)$ | $O(1)$ | 不安定 | 最悪保証があり in-place。定数倍はやや大きい |

クイックソートの追加メモリは再帰スタックの分です。素朴に書くと最悪で深さ $n$ になりますが（<Ref to="thm-quicksort-worst" />）、短い側だけを再帰する書き方にすれば必ず $O(\log n)$ に収まります（<Ref to="exr-tail-recursion" />）。表の値はこの工夫を前提としています。

実務での判断はおおむね次のとおりです。

- **標準ライブラリのソートを使う。** これが第一選択です。CPython の `list.sort` と Java のオブジェクト配列向け `Arrays.sort` は Timsort 系の安定マージソートで、入力に既に存在する連続した昇順・降順の並び（run）を検出して活用します。C++ の `std::sort` はイントロソート、Java の基本型配列向け `Arrays.sort` は 2 つのピボットを使うクイックソートです。安定性が必要かどうかで選択肢が分かれる点に注意してください。
- **最悪ケースの保証が要るとき**（応答時間の上限が契約になっている場合や、入力を敵対的に選ばれうる場合）はマージソートかヒープソート、あるいはイントロソートを選びます。
- **メモリが厳しいとき**はヒープソートかクイックソートです。マージソートの $\Theta(n)$ が払えない場面はあります。
- **小さい部分配列には挿入ソート。** 実際の高速な実装は、部分配列の長さが十数個を下回ったら再帰をやめて挿入ソートに切り替えます。$\Theta(n^2)$ でも定数倍が小さいので、小さい $n$ では勝ちます。

なお「ソート済みであること」は、それ自体が強力な前処理です。整列済み配列に対する二分探索は $O(\log n)$ で動きます（[探索アルゴリズム](/computer-science/algorithms/searching) の <Ref to="computer-science/algorithms/searching#thm-binary-cost" />）。1 回ソートしてから何度も検索する、という設計が成立するのは、$\Theta(n\log n)$ の投資を一度払えば、以後の検索が何回でも $O(\log n)$ で済むからです。また、分割統治は部分問題が重ならないときの手法で、部分問題が重複する場合は結果を再利用する [動的計画法](/computer-science/algorithms/dynamic-programming)（<Ref to="computer-science/algorithms/dynamic-programming#def-dp-formulation" />）が対応します。

## 8. 演習

<Exercise id="exr-inversion-expectation" difficulty="標準">
相異なる $n$ 個の要素を一様ランダムに並べた列 $a$ について、転倒数の期待値が

$$
\mathbb{E}[\operatorname{inv}(a)] = \frac{n(n-1)}{4}
$$

であることを示してください。またこれを使って、バブルソートの平均交換回数を求めてください。

<Solution>
添字の対 $(i,j)$（$i < j$）に対して、$a_i > a_j$ のとき $1$、そうでないとき $0$ を取る指示確率変数を $Y_{ij}$ とします。定義より $\operatorname{inv}(a) = \sum_{i<j} Y_{ij}$ です。

一様ランダムな順列において $\Pr[Y_{ij}=1] = 1/2$ を示します。全順列の集合上で、位置 $i$ と位置 $j$ の値を入れ替える写像 $\varphi$ を考えます。$\varphi$ を 2 回施すと元に戻る（$\varphi \circ \varphi$ が恒等写像）ので $\varphi$ は全単射であり、したがって一様分布を保ちます。そして $\varphi$ は $Y_{ij}$ の値を $0$ と $1$ で入れ替えます。よって $\Pr[Y_{ij}=1] = \Pr[Y_{ij}=0]$ であり、要素が相異なることから両者の和は $1$ なので、ともに $1/2$ です。

期待値の線形性（独立性は不要です）より

$$
\mathbb{E}[\operatorname{inv}(a)] = \sum_{i<j} \Pr[Y_{ij}=1] = \binom{n}{2}\cdot\frac{1}{2} = \frac{n(n-1)}{4}
$$

を得ます。

<Ref to="thm-bubble" /> の (2) よりバブルソートの交換回数は $\operatorname{inv}(a)$ に等しいので、平均交換回数も $n(n-1)/4$、すなわち $\Theta(n^2)$ です。最悪の場合の半分になるだけで、オーダーは改善しません。
</Solution>
</Exercise>

<Exercise id="exr-count-inversions" difficulty="難">
配列の転倒数 $\operatorname{inv}(a)$ を $O(n\log n)$ 時間で計算するアルゴリズムを、マージソートを改造して構成し、正しさを説明してください。

<Solution>
配列を前半 $L$ と後半 $R$ に分けると、転倒 $(i,j)$ は次の 3 種類に分類されます。

1. $i, j$ がともに前半にある。
2. $i, j$ がともに後半にある。
3. $i$ が前半、$j$ が後半にある（交差転倒）。

1 と 2 は再帰呼び出しが数えます。3 を、マージの最中に数えます。要点は、マージの時点で $L$ と $R$ は既にソート済みだという事実です。$R$ の先頭要素 `right[j]` を出力する場面では、`left[i] > right[j]` が成り立っています。$L$ はソート済みなので、まだ出力されていない `left[i], left[i+1], ..., left[-1]` はすべて `left[i]` 以上、したがってすべて `right[j]` より大きい。これらはいずれも元の配列で `right[j]` より前にあるので、交差転倒をちょうど `len(left) - i` 個作ります。

逆に、任意の交差転倒 $(x, y)$（$x \in L$、$y \in R$、$x > y$）はちょうど 1 回だけ数えられます。マージでは `left[i] <= right[j]` のとき左を出すので、$x > y$ である $x$ は $y$ より後に出力されます。つまり $y$ が出力される瞬間に $x$ は必ず未出力で、そのときの `len(left) - i` に数えられます。数えられるのはその 1 回だけです。

```python
def sort_and_count(a):
    if len(a) <= 1:
        return a[:], 0
    m = len(a) // 2
    left, c_left = sort_and_count(a[:m])
    right, c_right = sort_and_count(a[m:])
    merged, i, j, cross = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            cross += len(left) - i      # 残っている左側は全て right[j] より大きい
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, c_left + c_right + cross


assert sort_and_count([8, 3, 5, 1, 9, 2]) == ([1, 2, 3, 5, 8, 9], 9)
```

計算量はマージソートと同じ漸化式 $T(n) \le T(\lceil n/2\rceil) + T(\lfloor n/2 \rfloor) + cn$ に従うので、<Ref to="thm-mergesort" /> の証明と同じ議論で $O(n\log n)$ です。最後の `assert` は <Ref to="ex-bubble-trace" /> で手計算した転倒数 9 と一致します。二重ループで数えると $\Theta(n^2)$ かかるところを、ソートの副産物として得ているわけです。
</Solution>
</Exercise>

<Exercise id="exr-tail-recursion" difficulty="標準">
`quick_sort` は最悪の場合に再帰の深さが $n$ に達します（<Ref to="thm-quicksort-worst" />）。2 つの再帰呼び出しのうち**短い方だけ**を再帰で処理し、長い方はループで処理するように書き換えると、比較回数を変えずに再帰の深さを $O(\log n)$ に抑えられます。この実装を書き、深さの上界を証明してください。

<Solution>
```python
def quick_sort_bounded(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:            # 左が短い
            quick_sort_bounded(a, lo, p - 1)
            lo = p + 1                 # 右はループで処理
        else:                          # 右が短い
            quick_sort_bounded(a, p + 1, hi)
            hi = p - 1                 # 左はループで処理
    return a
```

処理する部分配列の集合は元の実装とまったく同じなので、`partition` の呼び出し回数も比較回数も変わりません。

深さの評価をします。長さ $m$ の部分配列を分割すると、2 つの部分の長さ $m_1, m_2$ は $m_1 + m_2 = m - 1$ を満たします（ピボット 1 個が抜けるため）。再帰するのは短い方なので、その長さは $\min(m_1, m_2) \le (m-1)/2 < m/2$ です。したがって再帰が 1 段深くなるたびに部分配列の長さは半分未満になります。長さ $n$ から始めて長さが $1$ 以下になれば再帰は止まるので、深さ $d$ では長さが $n/2^d$ 未満、これが $1$ 以下になるのは $d \ge \log_2 n$ のときです。よって再帰の深さは高々 $\lfloor \log_2 n \rfloor$ で、スタック使用量は $O(\log n)$ です。

これは末尾再帰の除去（tail call elimination）を手で行ったものと見ることができます。<Ref to="ex-quicksort-sorted" /> の整列済み入力に対しても、短い方（長さ $0$）を再帰し、長い方をループで回すので、深さは $1$ で済みます。実行時間が $\Theta(n^2)$ である点は変わりませんが、少なくともスタック溢れによる異常終了は防げます。
</Solution>
</Exercise>

<Exercise id="exr-stability" difficulty="易">
(a) `merge` の比較が `left[i] <= right[j]` である（`<` ではない）ことが、マージソートの安定性にとってなぜ必要かを説明してください。

(b) Lomuto 分割によるクイックソートが安定でないことを、3 要素の具体例で示してください。要素は「キーと付随データの組」とし、キーだけで比較するものとします。

<Solution>
**(a)** キーが等しい 2 要素 $x$（前半 $L$ に由来）と $y$（後半 $R$ に由来）を考えます。元の配列では $L$ の要素はすべて $R$ の要素より前にあるので、安定であるためには $x$ を $y$ より先に出力しなければなりません。比較が `left[i] <= right[j]` なら、キーが等しいとき条件は真になり左側の $x$ が先に出ます。もし `left[i] < right[j]` と書いていると、等しいときに `else` 節に入って右側の $y$ が先に出てしまい、順序が入れ替わります。等号をどちら側に付けるかという 1 文字が安定性を決めています。同じ半分に由来する 2 要素の順序は、<Ref to="thm-mergesort" /> の証明のとおり帰納法の仮定で保たれます。

**(b)** キー 2 の要素を $2_a, 2_b$、キー 1 の要素を $1_c$ とし、入力を

$$
a = (2_a,\; 2_b,\; 1_c)
$$

とします。`partition(a, 0, 2)` を追います。ピボットは `a[2]` すなわち $1_c$（キー 1）、$i = 0$ です。

- $j=0$：`a[0]` のキーは 2 で $2 \le 1$ は偽。何もしない。
- $j=1$：`a[1]` のキーは 2 で $2 \le 1$ は偽。何もしない。

ループを抜けて `a[0]` と `a[2]` を交換すると、配列は $(1_c,\; 2_b,\; 2_a)$、返り値は $p=0$ です。この後の再帰では、右側 $(2_b, 2_a)$ に対してピボット $2_a$ で分割しますが、$2 \le 2$ が真なので `a[1]` は自分自身と交換されて $i$ が 2 になり、最後に `a[2]` と `a[2]` を交換して並びは変わりません。最終出力は

$$
(1_c,\; 2_b,\; 2_a)
$$

です。入力ではキー 2 の要素が $2_a, 2_b$ の順だったのに、出力では $2_b, 2_a$ の順に入れ替わっています。よってこの実装は安定ではありません。原因は、分割の最後にピボットを境界へ移す交換が、遠く離れた 2 要素を入れ替えてしまうことにあります。要素を遠くへ動かせることがクイックソートの速さの源でしたが、その同じ性質が安定性を壊しています。
</Solution>
</Exercise>

## 参考文献

- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, *Introduction to Algorithms*, 4th ed., MIT Press, 2022 — 第 2 章（挿入ソートとマージソート）、第 7 章（クイックソートと期待計算量の解析）、第 8 章（比較ソートの下界、計数ソート、基数ソート）。
- D. E. Knuth, *The Art of Computer Programming, Volume 3: Sorting and Searching*, 2nd ed., Addison-Wesley, 1998 — 第 5 章（整列）、とくに 5.2（内部整列）。各手法の歴史的経緯と精密な定数の解析。
- C. A. R. Hoare, "Quicksort", *The Computer Journal* 5 (1962), 10–16. [DOI: 10.1093/comjnl/5.1.10](https://doi.org/10.1093/comjnl/5.1.10) — 考案者自身による原論文。
- J. L. Bentley, M. D. McIlroy, "Engineering a Sort Function", *Software: Practice and Experience* 23 (1993), 1249–1265. [DOI: 10.1002/spe.4380231105](https://doi.org/10.1002/spe.4380231105) — ピボット選択と重複要素の扱いを含む実装上の設計。
- D. R. Musser, "Introspective Sorting and Selection Algorithms", *Software: Practice and Experience* 27 (1997), 983–993 — イントロソート（クイックソートとヒープソートの切り替え）の提案論文。
- R. Sedgewick, K. Wayne, *Algorithms*, 4th ed., Addison-Wesley, 2011 — 第 2 章（ソート）。実装と実測に重心を置いた解説。

## Appendix: 分割統治の漸化式をまとめて解く

**マスター定理。** マージソートで現れた $T(n) = 2T(n/2) + \Theta(n)$ のような漸化式は、分割統治法のたびに顔を出します。毎回帰納法で解く代わりに、次の定理（<Ref to="computer-science/algorithms/complexity-and-big-o#thm-master" />）を使うと機械的に処理できます。$a \ge 1$、$b > 1$ を定数、$f(n)$ を非負関数とし、

$$
T(n) = a\,T(n/b) + f(n)
$$

とします（$n/b$ は $\lceil n/b \rceil$ や $\lfloor n/b \rfloor$ と読み替えてよい）。$\alpha = \log_b a$ と置くと、次が成り立ちます。

- ある $\varepsilon > 0$ について $f(n) = O(n^{\alpha - \varepsilon})$ ならば $T(n) = \Theta(n^{\alpha})$。（葉での仕事が支配的）
- $f(n) = \Theta(n^{\alpha})$ ならば $T(n) = \Theta(n^{\alpha}\log n)$。（各段が均等に効く）
- ある $\varepsilon > 0$ について $f(n) = \Omega(n^{\alpha + \varepsilon})$ で、かつある $c < 1$ と十分大きいすべての $n$ について $a f(n/b) \le c f(n)$ が成り立つならば $T(n) = \Theta(f(n))$。（根での仕事が支配的）

**マージソートへの適用。** $a = 2$、$b = 2$、$f(n) = \Theta(n)$ なので $\alpha = \log_2 2 = 1$、$f(n) = \Theta(n^{1}) = \Theta(n^{\alpha})$ で第 2 の場合に当たり、$T(n) = \Theta(n\log n)$ を得ます。<Ref to="thm-mergesort" /> の帰納法と同じ結論です。

**分割の偏りが与える影響。** クイックソートの最悪ケースは $T(n) = T(n-1) + \Theta(n)$ で、これは $n/b$ の形をしていないためマスター定理の対象外ですが、直接展開すれば $T(n) = \Theta(n^2)$ です。一方、分割が常に「$1:9$」に偏るという（一見すると悪そうな）場合は $T(n) = T(n/10) + T(9n/10) + \Theta(n)$ で、再帰木の深さが $\log_{10/9} n = \Theta(\log n)$、各段のコストが $O(n)$ なので $T(n) = \Theta(n\log n)$ のままです。定数比の偏りは対数の底を変えるだけで、オーダーを壊しません。クイックソートが「そこそこの分割」でも十分速い理由がここにあります。破綻するのは、分割が「$1$ 個と残り全部」のように定数比を保てなくなるときだけです。

**注意点。** 第 3 の場合の正則条件（$a f(n/b) \le c f(n)$）は飾りではありません。$f$ が振動する場合など、これを満たさない例では結論が成り立たないことがあります。また 3 つの場合の隙間（たとえば $f(n) = \Theta(n^{\alpha}\log n)$）はマスター定理では扱えず、再帰木を直接評価するか、より一般の Akra–Bazzi の方法が必要です。証明と精密な形は Cormen らの第 4 章にあります。