· 開発

クイックソートはいつO(n²)になるのか：標準ソートが最悪ケースを防ぐ仕組み

ソート済み入力、median-of-3 killer、敵対的な比較関数でクイックソートは二次時間になります。introsortの深さ制限と、C++・Rust・Go・Javaの文書が保証する範囲を解説します。

開発アルゴリズム

クイックソートは平均O(n log n)、最悪O(n²)と習います。最悪ケースはどんな入力で起き、言語の標準ソートにも同じ危険はあるのでしょうか。クイックソートそのものは今でも二次時間になり得ます。多くの標準ライブラリはこれを防いでいますが、その保証が仕様にあるのか、実装の説明にとどまるのかは言語によって異なります。

分割が片側に偏るとき

クイックソートはピボットを選び、残りの要素をピボットより小さい側と大きい側に分け、それぞれを再びソートします。毎回ほぼ半分に分かれれば深さは約log₂ Nです。各段の処理量はNに比例するため、全体はN log Nになります。

分割が片側に偏り続け、深さがNに比例すると、全体はN²になります。

分かりやすい例は、常に先頭要素をピボットにする実装へソート済みの配列を渡す場合です。ピボットが毎回最小値になるので、片側は常に空になります。比較回数は次のとおりです。

(n−1)+(n−2)+…+1 = n(n−1)/2

n = 1,000なら499,500回です。

ピボットを工夫しても最悪ケースは残る

先頭・中央・末尾の3要素の中央値をピボットにする方法を「3点の中央値」（median-of-3）と呼びます。ソート済みの入力はうまく分割できますが、最悪ケースはなくなりません。

David Musserは1997年の論文で、Nが4の倍数のとき、median-of-3の分割が毎回2要素しか切り出せなくなる順列を示しました。median-of-3を狙い撃ちするこの入力は「median-of-3 killer」と呼ばれます。論文は、この入力でmedian-of-3のクイックソートにΩ(N²)の時間がかかることを示しています。当時のHPのSTLのsortもこの方式だったと書かれています。

ピボットを無作為に選べば、悪い分割が続く可能性は低くなります。ただし、最悪時間の上限はN²のままです。M. D. McIlroyは1999年の論文で、比較の順序を見ながら値をその場で決める敵対的な比較関数を作り、Cのqsortを二次時間に追い込みました。いくつかの前提のもとでは、無作為なピボットにも通用します。

論文の表では、Irix 6.4のmedian-of-3のqsortは、この比較関数に対して約0.25n²回比較しました。これは1998年頃の一つの実装に対する測定値です。一般的な係数でも、その実装について証明された究極の最悪ケースでもありません。

深さに上限を設けるイントロソート

Musserが提案したイントロソート（introsort）は、median-of-3のクイックソートと同じように分割し、深さが2⌊log₂ N⌋に達したら残りの区間をヒープソートに引き渡します。ヒープソートは最悪でもN log Nなので、論文はイントロソートの最悪時間がΘ(N log N)であることを証明しています。ほとんどの入力ではクイックソートとほぼ同じように動きます。

ヒープの格納順序はヒープはソート済みリストではないで扱いました。論文によれば、イントロソートも安定ソートではありません。

言語の文書が保証する範囲

C++。 かつてのstd::sortの計算量は「平均でおよそN log N回の比較」で、最悪ケースが重要ならstable_sortかpartial_sortを使うよう求める脚注が付いていました。2007年に起票されたLWG issue 713は、イントロソートを根拠にO(N log N)へ改めるよう提案しました。解決案は2008年の委員会草案に取り込まれています。現在の作業草案の[sort]はO(N log N)回の比較と射影を要求しますが、アルゴリズムは指定していません。

Rust。 slice::sort_unstableの文書本文には、不安定でインプレース、最悪O(n log n)と書かれています。クイックソートとヒープソートを組み合わせたipnsortを基にしているという説明は、別の「Current implementation」の項にあります。

Go。 sort.Sortの文書には、LessとSwapをO(n log n)回呼び出すと書かれています。pattern-defeating quicksortで書き直したことはGo 1.19のリリースノートに記録されています。

Java。 JDK 8のArrays.sort(int[])の実装ノートは、Dual-Pivot Quicksortが「他のクイックソートを二次の性能に劣化させる多くのデータ」でO(n log n)の性能を出すと説明します。JDK 25では「すべてのデータ」と書かれています。ただし、Arraysクラスの文書は、こうした説明を仕様ではなく実装ノートとして扱うよう述べています。

自分で実装するなら

自分でクイックソートを実装するなら、ピボットの選び方だけに頼らず、深さの上限と代わりのアルゴリズムを組み合わせるほうが安全です。標準ソートについては、最悪ケースの保証が仕様にあるのか、変更され得る実装ノートにとどまるのかを、使用中のバージョンの文書で確認してください。

本文の文書は2026年10月5日に確認しました。

参照した論文と文書

ブログへ