O[n log(n)] の壁を超える！「比較しないソート」【ソートアルゴリズム入門】#12

私たちは「壁」にぶつかっている

これまで、このソートアルゴリズム入門シリーズでは、様々なソートアルゴリズムを学んできました。

単純ソート（バブルソートなど）: $O[n^2]$ の世界
高速ソート（マージソート、ヒープソート）: $O[n \log n]$ の世界

特にマージソートやヒープソートの $O[n \log (n)]$ という計算量は、$O[n^2]$ とは比べ物にならない圧倒的な速さでした。

ここで、一つの疑問が生まれます。

「$O[n \log n]$ より速いソートアルゴリズムは存在しないのだろうか？」

「究極の $O[n]$ （データ数に比例するだけ）のソートは無理なのだろうか？」

実は、これまで私たちが学んできたアルゴリズムには、ある「共通の制約」がありました。そして、その制約こそが $O[n \log n]$ という「理論上の壁」を生み出していたのです。

　その方法とは、何なのか？この記事では、その「壁」の正体を解き明かし、その壁を超えるための全く新しいアプローチを考えてみましょう。

12 記事

シリーズ

ソートアルゴリズム

ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...

1. 私たちが使ってきた「比較ソート」とは？

まず、これまで学んだアルゴリズムを振り返ってみてください。

バブルソート: 隣同士の要素を比較して交換した。
挿入ソート: 挿入先の要素と比較しながら、適切な場所を探した。
マージソート: 2つのソート済みリストの先頭を比較して、小さい方を採用した。
クイックソート: ピボットと比較して、大小2つのグループに分けた。
ヒープソート: 親と子のノードを比較して、ヒープ構造を維持した。

お気づきでしょうか？これらすべては、

「2つの要素 A と B を『比較』し（A < B ?）、その結果によって処理を変える」

という操作を基本にしています。

このようなアルゴリズムを、まとめて「比較ソート（Comparison Sort）」と呼びます。

2. 理論上の壁：なぜ $ O[n \log n]$ を超えられないのか

では、なぜ「比較ソート」は $O(N \log N)$ より速くなれないのでしょうか？

これは「アルゴリズムが賢くないから」ではなく、「数学的な限界」があるからです。Shutterstock

決定木（けっていぼく）という考え方

難しい数学は抜きにして、決定木という考え方でイメージしてみましょう。

3つの異なるデータ [a, b, c] をソートすることを考えます。

最終的な正しい並び順は、[a, b, c] [a, c, b] [b, a, c] [b, c, a] [c, a, b] [c, b, a] の6パターンあります。

アルゴリズムの仕事は、この6パターンのうち、どれが正解かを「比較」だけを頼りに突き止めることです。

最初の比較:a < b ですか？
- Yes (aがbより小さい) → この時点で、[b, a, c] [b, c, a] [c, b, a] の可能性が消える。
- No (aがbより大きい) → この時点で、[a, b, c] [a, c, b] [c, a, b] の可能性が消える。

このように、「比較」という「Yes / No」の質問を繰り返すことで、可能性を絞り込んでいきます。この分岐の様子が、まさしく「木（ツリー）」のようになります。

比較回数の限界

データが $n$ 個ある場合、考えられる並び順の総パターンは $n !$（nの階乗）通りというとてつもない数になります。

アルゴリズムは、この $n !$ 通りの可能性の迷路から、たった1つの正解を「比較」だけで見つけなければなりません。

賢いアルゴリズム（マージソートなど）は、この迷路をできるだけ効率的に（二分探索のように）進みます。

数学的に、$n !$ 通りの選択肢を二択（比較）だけで絞り込む場合、最低でも $ \log_2(n!)$ 回の比較が必要であることが証明されています。

そして、この $ \log_2(n!)$ は、計算量で表すと $O[n \log n] $とほぼ同じになるのです。気になる人は検索してみてください。(問い合わせフォームで意見があれば、記事化するかも..)

イメージは、第7回のなぜlogが出てくるの？に近いです。

なぜ計算量がn log(n)？”log”が出てくる訳をわかりやすく紹介【ソートアルゴリズム入門】#7

O[n^2] を超える高速なソート（クイックソート等）は O[n log n] と呼ばれます。なぜ突然log（対数）が出てくるのか？その秘密は「半分に分ける」という最強の戦略「分割統治法」にありました。log の正体を視覚的に解き明かします。

結論:

「比較」だけを武器に戦う限り、どんなに賢いアルゴリズム（比較ソート）であっても、最悪の場合 $O(n \log n)$ 回の”質問”（比較）が数学的に必要となってしまう。これが「理論上の壁」の正体です。

3. 壁を超える：「比較しないソート」という新戦略

$O(N \log N)$ が限界なら、どうすれば $O(N)$ のような夢の速度に到達できるのでしょうか？

答えは単純です。

「”比較” をするのをやめる」のです。

比較をやめて思いもよらない別の手段を取る。有名作品のセリフを借りるなら、『おれは比較をやめるぞ！』といったところでしょうか。

ここで、「比較しないで、どうやって大小関係を？」と混乱すると思います。

「比較ソート」は、データの中身が「リンゴ」でも「名前」でも「数字」でも、とにかくA < Bというルールさえあれば動作しました。

「比較しないソート（Non-Comparison Sort）」は、この汎用性を捨てる代わりに、データが持つ「特定の性質」を利用して、一気に効率を上げます。

例：もしデータが「0から9までの整数」とわかっていたら？

比較ソート: [3, 1, 5, 2, 1] という配列を見て、「3 と 1 を比較して…」と考えます。
比較しないソート:
1. データを入れるための「バケツ」を10個（0用, 1用, … 9用）用意します。
2. [3, 1, 5, 2, 1] を順番に見て、3 を「3のバケツ」に、1 を「1のバケツ」に…と放り込んでいきます。
3. 最終的に、バケツはこうなります。
  - 1のバケツ: [1, 1]
  - 2のバケツ: [2]
  - 3のバケツ: [3]
  - 5のバケツ: [5]
4. 「0のバケツ」から順番に中身を取り出せば、[1, 1, 2, 3, 5] とソートが完了します。