クイックソート

クイックソート

クイックソート アルゴリズムのアニメーション視覚化。水平線はピボット値です。
クラス	ソートアルゴリズム
最悪の場合の パフォーマンス	${\displaystyle O(n^{2})}$
最高の パフォーマンス	${\displaystyle O(n\log n)}$(単純なパーティション) または(3 方向のパーティションと等しいキー)${\displaystyle O(n)}$
平均的 なパフォーマンス	${\displaystyle O(n\log n)}$
最悪の場合の 空間複雑度	${\displaystyle O(n)}$補助的（素朴）補助的（Hoare 1962） ${\displaystyle O(\log n)}$
最適	いいえ

クイックソートは、効率的で汎用的なソートアルゴリズムです。クイックソートは、1959年にイギリスのコンピュータ科学者トニー・ホーアによって開発され^[1]、1961年に公開されました。 ^[2]これは、現在でもソートによく使用されるアルゴリズムです。全体的に、ランダム化されたデータ、特に大規模な分布の場合、マージソートやヒープソートよりもわずかに高速です。 ^[3]

クイックソートは分割統治アルゴリズムです。配列から「ピボット」要素を選択し、他の要素をピボットより小さいか大きいかに応じて2つのサブ配列に分割することによって機能します。このため、パーティション交換ソートと呼ばれることもあります。^[4]次に、サブ配列を再帰的にソートします。これはインプレースで実行でき、ソートを実行するために 少量の追加メモリを必要とします。

クイックソートは比較ソートです。つまり、「より小さい」関係 (正式には全順序) が定義されている任意のタイプの項目をソートできます。要素aとb は、それらの相対順序が以前の比較結果の推移閉包で取得された場合にのみ交換されるため、比較ベースのソートです。クイックソートの実装のほとんどは安定していません。つまり、等しいソート項目の相対順序は保持されません。

クイックソートの数学的分析によれば、平均して、アルゴリズムはn 個の項目をソートするために 回の比較を行うことになります。最悪の場合、比較が行われます。 ${\displaystyle O(n\log {n})}$${\displaystyle O(n^{2})}$

クイックソートアルゴリズムは、1959年にモスクワ国立大学の客員学生だったトニー・ホーアによって開発されました。当時、ホーアは国立物理学研究所の機械翻訳プロジェクトに取り組んでいました。翻訳プロセスの一環として、磁気テープ上にアルファベット順に保存された露英辞書でロシア語の文章中の単語を調べる前に、単語をソートする必要がありました。^{[5]彼は、最初のアイデアである}挿入ソートが遅いことに気づき、新しいアイデアを思いつきました。彼は、パーティション部分をマーキュリーオートコードで記述しましたが、ソートされていないセグメントのリストの処理に問題がありました。イギリスに戻ると、彼はシェルソートのコードを書くように頼まれました。ホーアは上司に、自分はもっと速いアルゴリズムを知っていると伝えたところ、上司は彼が知らないと賭けました。上司は最終的に彼が賭けに負けたことを認めました。ホーアは、このアルゴリズムに関する論文を、1962年のコンピュータジャーナル第5巻第1号、10～16ページで発表しました。その後、ホーアはALGOLとその再帰機能について学び、当時のトップクラスのコンピュータサイエンス雑誌であるCommunications of the Association for Computing Machinery^{にALGOLのアルゴリズムの改良版を発表することができた。 [2] [6]} ALGOLのコードは、Communications of the ACM (CACM)、第4巻、1961年7月号、321ページの「アルゴリズム63: パーティション」および「アルゴリズム64: クイックソート」に掲載されている。

クイックソートは広く採用され、例えばUnixではデフォルトのライブラリソートサブルーチンとして登場しました。そのため、Cの標準ライブラリサブルーチンqsort ^[7]やJavaのリファレンス実装にその名前が付けられました。

ロバート・セジウィックの1975年の博士論文はクイックソートの研究におけるマイルストーンと考えられており、サンプルソート、ヴァン・エムデンによる適応型パーティショニング^[8]、および比較とスワップの期待数の導出を含むさまざまなピボット選択スキームの分析に関連する多くの未解決の問題を解決しました。^[7] ジョン・ベントレーとダグ・マキロイは1993年に、等しい要素を処理する手法や、 9つの要素のサンプルを3つずつのグループに分割し、3つのグループから3つの中央値の中から中央値を選択する擬似中央値9と呼ばれるピボットスキームなど、プログラミングライブラリで使用するためにさまざまな改良を組み込みました。 ^[7]ベントレーは、ニコ・ロミュートによるものだと彼が考えている、よりシンプルでコンパクトなパーティショニングスキームを、著書「プログラミングパール」で説明しています。後にベントレーは、ホーアのバージョンを何年も使っていたが、実際には理解していなかったが、ロミュートのバージョンは正しいことが証明できるほど単純だったと書いています。^[9]ベントレーは同じエッセイの中でクイックソートを「私が書いた中で最も美しいコード」と評した。ロミュートのパーティション方式もアルゴリズム入門の教科書で普及したが、平均して3倍のスワップを行い、すべての要素が等しい場合は実行時間がO ( n2 )に低下するため、ホーアの方式より^{劣っている。 [10] [自費出版のソース? ]マキロイはさらに1998年に}アンチクイックソート( aqsort )関数を作成し、これは1993年のクイックソートの変種でさえも敵対的なデータをオンザフライで生成することで一貫して二次動作に誘導した。^[11]

クイックソートは、分割ルーチンに基づいて配列をソートする分割統治アルゴリズムの一種です。この分割の詳細は多少異なるため、クイックソートは実際には密接に関連したアルゴリズムのファミリーです。少なくとも 2 つの要素の範囲に適用すると、分割によって 2 つの連続する空でないサブ範囲に分割され、最初のサブ範囲のどの要素も 2 番目のサブ範囲のどの要素よりも大きくなることはありません。この分割を適用した後、クイックソートはサブ範囲を再帰的にソートします。その際、この時点で既に最終位置にあることがわかっている分割ポイントの要素をサブ範囲から除外する場合もあります。再帰的な性質のため、クイックソート (分割ルーチンと同様) は、最終的な目標が完全な配列をソートすることであっても、より大きな配列内の範囲に対して呼び出せるように定式化する必要があります。インプレースクイックソートの手順は次のとおりです。

1. 範囲に 2 要素未満の要素がある場合は、何もする必要がないため、すぐに戻ります。その他の非常に短い長さの場合は、特殊なソート方法が適用され、残りの手順はスキップされる可能性があります。
2. それ以外の場合は、範囲内で発生するピボットと呼ばれる値を選択します(選択の正確な方法はパーティション ルーチンによって異なり、ランダム性が含まれる場合があります)。
3. 範囲を分割します。分割点を決定しながら、その要素を並べ替えます。ピボットより小さい値を持つすべての要素は分割の前に配置され、ピボットより大きい値を持つすべての要素は分割の後に配置されます。ピボットと等しい要素はどちらの方向にも配置できます。ピボットのインスタンスが少なくとも 1 つ存在するため、ほとんどの分割ルーチンでは、分割点の値がピボットと等しくなり、最終的な位置にあることが保証されます (ただし、元の値より厳密に小さいサブ範囲が生成されている限り、クイックソートの終了はこれに依存しません)。
4. クイックソートを分割点までのサブ範囲とそれ以降のサブ範囲に再帰的に適用し、分割点のピボットに等しい要素を両方の範囲から除外することもできます。(分割によって境界付近に、すべての要素がピボットに等しいことがわかっているより大きなサブ範囲が生成される場合、これらも除外できます。)

パーティション ルーチンの選択 (ピボットの選択を含む) や、上記で完全には指定されていないその他の詳細は、アルゴリズムのパフォーマンスに影響を及ぼす可能性があり、特定の入力配列では大きな影響を及ぼす可能性があります。したがって、クイックソートの効率性について説明するには、まずこれらの選択を指定する必要があります。ここでは、2 つの特定のパーティション方法について説明します。

この方式はニコ・ロミュートによるもので、ベントレーの著書「プログラミング・パールズ」^[12]とコーメンらの著書「アルゴリズム入門」 ^[13]で普及しました。ほとんどの定式化では、この方式は配列の最後の要素をピボットとして選択します。アルゴリズムは、別のインデックスjを使用して配列をスキャンするときにインデックスiを維持し、 loからi-1 （両端を含む）の要素がピボットより小さく、iからj（両端を含む）の要素がピボットと等しいかそれより大きくなります。この方式はよりコンパクトで理解しやすいため、入門書でよく使用されますが、たとえばすべての要素が等しい場合など、ホーアの元の方式よりも効率は悪くなります。^[14]配列がすでに整列している場合は、パーティションが最悪のものになるため、この方式によるクイックソートの複雑度はO（n ²）に低下します。 ^[10]パフォーマンスを向上させるために、ピボットの選択方法、等しい要素の処理方法、小さな配列に対する挿入ソートなどの他のソートアルゴリズムの使用など、さまざまなバリエーションが提案されています。擬似コードでは、配列Aのloからhiまでの要素（両端を含む）をソートするクイックソートは次のように表現できます。^[13]

// 配列（の一部）をソートし、それをパーティションに分割し、それらをソートする
アルゴリズムquicksort(A, lo, hi)は 
  // インデックスが正しい順序になっていることを確認する
  if lo >= hi || lo < 0 then 
    戻る
    
  // 配列を分割してピボットインデックスを取得します
  p := パーティション(A, lo, hi)
      
  // 2つのパーティションをソートします
  quicksort(A, lo, p - 1) // ピボットの左側
  quicksort(A, p + 1, hi) // ピボットの右側

// 配列を2つのパーティションに分割します。
アルゴリズムpartition(A, lo, hi)は 
  pivot:=A[hi]です。 // 最後の要素をピボットとして選択します。

  // 一時的なピボットインデックス
  私 := lo

  for j := lo to hi - 1 do  
    // 現在の要素がピボット以下の場合
    if A[j] <= pivot then  
      // 現在の要素を一時ピボット インデックスの要素と交換
      swap A[i] with A[j]
       // 一時ピボット インデックスを前方に移動する
      私 := 私 + 1

  // ピボットを最後の要素と交換します
  swap A[i] with A[hi]
   return i // ピボットのインデックス

配列全体のソートはquicksort(A, 0, length(A) - 1)によって実行されます。

トニー・ホーアが説明したオリジナルの分割スキームでは、分割される配列の両端から始まる 2 つのポインタ (範囲のインデックス) を使用し、反転が検出されるまで互いに近づきます。反転とは、1 つ目のポインタのピボットよりも大きい要素と、2 つ目のポインタのピボットよりも小さい要素のペアです。この時点で、1 つ目のポインタがまだ 2 つ目のポインタより前にある場合、これらの要素は互いに対して順序が間違っているため、交換されます。^[15]この後、ポインタは内側に移動し、反転の検索が繰り返されます。最終的にポインタが交差すると (最初のポインタが 2 つ目のポインタより後ろを指す)、交換は実行されません。交差したポインタの間に分割点がある有効な分割が見つかります (交差したポインタの間にある可能性のあるエントリはすべてピボットと等しく、形成された両方のサブ範囲から除外できます)。この定式化では、1 つのサブ範囲が元の範囲全体であることが判明する可能性があり、その場合、アルゴリズムが先に進めなくなります。したがって、ホーアは、最後に、ピボット要素 (まだ元の位置にある) を含むサブ範囲のサイズを、そのピボットを除外し、必要に応じてそれを分離に最も近いサブ範囲要素と交換することによって縮小できることを規定しています。これにより、クイックソートの終了が保証されます。

この元の説明に関して、実装では、小さいながらも重要な変更が加えられることがよくあります。特に、以下に示すスキームでは、反転の候補にピボットに等しい要素が含まれています (したがって、「より大きい」と「より小さい」の代わりに、「以上」と「以下」のテストがそれぞれ使用されます。定式化では、厳密な比較演算子^{[明確化が必要]}の使用によって実際に反映されるrepeat ... untilではなくdo ... whileを使用しているためです)。ピボットに等しい要素を交換する理由はありませんが、この変更により、ポインタ自体のテストを省略できます。このテストは、範囲外にならないようにするために必要です。実際、範囲内にピボット値のインスタンスが少なくとも 1 つ存在するため、包括的テストを使用する場合、どちらのポインタの最初の前進もこのインスタンスを通過できません。交換が実行されると、交換されたこれらの要素は両方とも、それらを見つけたポインタより厳密に先行するため、そのポインタが外れることがなくなります。 (後者は、使用するテストとは無関係に当てはまるため、最初の反転を探すときにのみ包括的テストを使用することもできます。ただし、全体にわたって包括的テストを使用すると、範囲内のすべての要素が等しい場合に中央付近の分割が確実に見つかるため、等しい要素が多数ある配列をソートする場合に重要な効率性が得られます。) 前進しない分離が生じるリスクは、Hoare が説明した方法とは異なる方法で回避されます。このような分離は、反転が見つからず、最初の反復で両方のポインタがピボット要素に前進する場合にのみ発生します (その場合、ポインタは交差したと見なされ、交換は行われません)。

擬似コードでは、^[13]

// 配列（の一部）をソートし、それをパーティションに分割し、それらをソートする
アルゴリズムquicksort(A, lo, hi)は、 
   lo >= 0 && hi >= 0 && lo < hiの場合、
    p := パーティション(A, lo, hi)
    quicksort(A, lo, p) // 注: ピボットが含まれるようになりました
    クイックソート(A, p + 1, hi)

// 配列を2つのパーティションに分割します。
アルゴリズムpartition(A, lo, hi)は、 // ピボット値
  pivot:=A[lo]です。  
  // 最初の要素をピボットとして選択します。

  // 左インデックス
  私 := lo - 1

  // 右インデックス
  j := hi + 1

  永遠にループします 
    // 左のインデックスを少なくとも1回右に移動し、
    左のインデックスの要素がピボットより小さい
    間、 i := i + 1 を実行します(A[i] < pivot)
    
    // 右のインデックスを少なくとも1回左に移動し、
    右のインデックスの要素がピボットより大きい
    間、 A[j] > pivotでj := j - 1 を実行します。

    // インデックスが交差している場合は、
     i >= jの場合は j を返します
    
    // 左と右のインデックスの要素を入れ替える
    swap A[i] with A[j]

配列全体はquicksort(A, 0, length(A) - 1)によってソートされます。

Hoare の方式は、平均して 3 倍少ないスワップを実行するため、Lomuto のパーティション方式よりも効率的です。また、前述のように、示された実装では、すべての値が等しい場合でもバランスの取れたパーティションが作成されます。^{[10] [自己出版ソース? ] 、Lomuto の方式ではそうではありません。Lomuto のパーティション方式と同様に、Hoare のパーティション分割でも、ピボットが最初または最後の要素として選択された場合、すでにソートされた入力に対して Quicksort が}O ( n ² )に低下します。ただし、中央の要素をピボットとして使用すると、ソートされたデータは同じサイズのパーティションで (ほぼ) スワップされず、Quicksort の最良の動作、つまりO ( n log( n ))になります。他のパーティション分割と同様に、Hoare のパーティション分割では安定したソートは生成されません。この方式では、ピボットの最終的な位置は、必ずしも返されるインデックスにあるとは限りません。これは、ピボットとピボットに等しい要素がパーティション ステップの後にパーティション内のどこにでも配置され、再帰によって 1 つの要素を持つパーティションの基本ケースに到達するまでソートされない可能性があるためです。したがって、メイン アルゴリズムが再帰する次の 2 つのセグメントは、 Lomuto 方式の(lo..p-1)と(p+1..hi)ではなく、(lo..p) (要素 ≤ ピボット)と(p+1..hi) (要素 ≥ ピボット)です。

後続の再帰（前の段落の拡張）

メイン アルゴリズムが再帰する次の 2 つのセグメントについて、もう少し詳しく説明します。範囲外にならないように「do...while」ループで厳密な比較演算子 (>、<) を使用しているため、ピボット自体がパーティション関数内の他の要素と入れ替わる可能性があります。したがって、パーティション関数で返されるインデックスは、必ずしも実際のピボットの場所ではありません。[5, 2, 3, 1, 0]の例を考えてみましょう。このスキームに従うと、最初のパーティションの後、配列は[0, 2, 1, 3, 5]になり、返される「インデックス」は 2 (つまり数字 1) ですが、パーティションを開始するために選択した実際のピボットは数字 3 でした。この例では、パーティション関数の返されたインデックスを後続の再帰に含める必要があることがわかります。その結果、(lo..p)と(p+1..hi)を再帰するか、(lo..p - 1)と(p..hi)を再帰するかという選択肢が提示されます。 どちらのオプションを選択するかは、インデックスが交差するときにパーティション関数で返すインデックス ( iまたはj ) と、パーティション関数でピボットを選択する方法 ( floorまたはceiling )によって決まります。

まず、複数の同一要素が存在する配列[0, 0]をソートする例で、 (lo..p)と(p+1..hi)の再帰の選択について検討してみましょう。パーティション関数でインデックスが交差した後にインデックス i (「後者の」インデックス) が返される場合、最初のパーティションの後にインデックス 1 が返されます。(lo..p)のその後の再帰は(0, 1) になり、これはまったく同じ配列[0, 0]に対応します。無限再帰を引き起こす非前進分離が生成されます。したがって、(lo..p)と(p+1..hi)の再帰では、再帰の左半分に返されたインデックスが含まれるため、非前進シナリオで「末尾」を除外するのはパーティション関数の役割であることは明らかです。つまり、インデックス j (インデックスが交差する場合の「前者の」インデックス) が i の代わりに返される必要があります。同様のロジックで、すでにソートされた配列[0, 1]の例を考えるとき、ポインターが「後者」ではなく「前者」で停止するように、ピボットの選択は「floor」にする必要があります (ピボットとして「ceiling」を使用すると、インデックス 1 が返され、(lo..p)に含まれ、無限再帰が発生します)。最後の要素をピボットとして選択することを避ける必要があるのも、まったく同じ理由です。

(lo..p - 1)と(p..hi)の再帰の選択は、上記とまったく同じロジックに従います。再帰の右半分には返されたインデックスが含まれるため、非前進シナリオで「ヘッド」を除外するのはパーティション関数の役割です。パーティション関数のインデックス i (インデックスが交差した後の「後者の」インデックス) を返す必要があり、ピボットとして「天井」を選択する必要があります。複数の同一要素が存在する配列 ( [0, 0] ) と、すでにソートされた配列[0, 1]をそれぞれソートする例を考えると、2 つのニュアンスは再び明らかになります。同じ理由で、再帰のバージョンでは、最初の要素をピボットとして選択することは避ける必要があることに注意してください。

クイックソートのごく初期のバージョンでは、パーティションの最も左の要素がピボット要素として選択されることがよくありました。残念ながら、これはすでにソートされた配列で最悪の動作を引き起こしますが、これはかなり一般的な使用例です。^[16]この問題は、ピボットにランダムなインデックスを選択するか、パーティションの中央のインデックスを選択するか、(特にパーティションが長い場合は)パーティションの最初、中央、最後の要素の中央値をピボットに選択することで簡単に解決しました ( Sedgewickの推奨どおり)。^[17]この「3 つの中央値」ルールは、ソートされた (または逆ソートされた) 入力の場合に対処し、入力の順序に関する情報が不明な場合に、単一の要素を選択するよりも最適なピボット (真の中央値) をより正確に推定します。

Lomuto パーティションの 3 つの中央値コード スニペット:

mid := ⌊(lo + hi) / 2⌋
 A[mid] < A[lo]の場合
    A[lo]とA[mid]を入れ替える
A[hi] < A[lo]の場合
    A[lo]をA[hi]と入れ替える
A[mid] < A[hi]の場合
    A[mid]をA[hi]と入れ替える
ピボット := A[hi]

最初に中央値を代入しA[hi]、次にその新しい値をA[hi]ピボットに使用します (これは、上記で示した基本的なアルゴリズムと同じです)。

具体的には、ランダムピボット選択でn個の要素をソートするために必要な比較の予想回数は（§ ランダム化クイックソートの分析を参照）、 1.386 n log nである。3 の中央値ピボットでは、予想スワップ回数が 3 パーセント増加するという代償を払って、これをC _{n , 2} ≈ 1.188 n log n^{に減らすことができる。[ 7]より大きな配列の場合、さらに強力なピボットルールは、} 9 番目の、つまり再帰的な 3 の中央値（Mo3）を選択することである。これは次のように定義される^[7]

ninether( a ) = median(Mo3(first ⁠1/3⁠の) , Mo3(中間⁠1/3⁠の) , Mo3(最終⁠1/3⁠の) )

ピボット要素の選択は、整数オーバーフローの存在によっても複雑になります。ソートされるサブ配列の境界インデックスが十分に大きい場合、中間インデックスの単純な式( lo + hi )/2はオーバーフローを引き起こし、無効なピボットインデックスを提供します。これは、たとえば、中間要素のインデックスにlo + ( hi − lo )/2 を使用することで克服できますが、より複雑な計算が必要になります。ピボット要素を選択する他の方法でも同様の問題が発生します。

上で説明した Lomuto パーティション スキームなどのパーティション アルゴリズムでは (適切なピボット値を選択するアルゴリズムであっても)、繰り返し要素を多数含む入力に対してクイックソートのパフォーマンスが低下します。入力要素がすべて等しい場合、この問題は明らかに顕著になります。つまり、各再帰で、左のパーティションは空 (ピボットより小さい入力値がない) で、右のパーティションは 1 つの要素だけ減少します (ピボットが削除される)。その結果、Lomuto パーティション スキームでは、等しい値の配列をソートするのに2 乗の時間がかかります。ただし、Hoare パーティション スキームなどのパーティション アルゴリズムでは、繰り返し要素によって一般にパーティション分割が改善され、ピボットに等しい要素の不要なスワップが発生する可能性はありますが、繰り返し要素の数が増えるにつれて実行時間は通常減少します (メモリ キャッシュによってスワップ オーバーヘッドが削減されます)。すべての要素が等しい場合、Hoare パーティション スキームでは要素が不必要にスワップされますが、上記の Hoare パーティションのセクションで説明したように、パーティション分割自体は最善です。

ロミュート分割方式問題 (オランダ国旗問題^[7]とも呼ばれる) を解決するには、値をピボットより小さい値、ピボットと等しい値、ピボットより大きい値の 3 つのグループに分ける、代替の線形時間分割ルーチンを使用できます。 (Bentley と McIlroy はこれを「ファット分割」と呼び、これはバージョン 7 Unixのqsortですでに実装されています。^[7] ) ピボットと等しい値はすでにソートされているため、小さいパーティションと大きいパーティションのみを再帰的にソートする必要があります。疑似コードでは、クイックソート アルゴリズムは次のようになります。

// 配列（の一部）をソートし、それをパーティションに分割し、それらをソートします。
アルゴリズムquicksort(A, lo, hi)は
  、 lo >= 0 && lo < hiの場合、 
    lt, gt := partition(A, lo, hi) です。// 複数の戻り値
    クイックソート(A, lo, lt - 1)
    クイックソート(A, gt + 1, hi)

// 配列を3つのパーティションに分割します。
アルゴリズムpartition(A, lo, hi)は、 // ピボット値
  pivot:=A[(lo + hi) / 2]です。 
  // 中央の要素をピボットとして選択します（整数除算）
  
  // 小さい、等しい、大きいインデックス
  lt := lo
  等しい := lo
  gt := こんにちは
  
  // すべての要素をピボットで反復して比較します
  while eq <= gt do 
    if A[eq] < pivot then 
      // 等しいか小さいインデックスの要素を交換します
      swap A[eq] with A[lt]
       // 小さい方のインデックスを増やします
      lt := lt + 1
      // 等インデックスを増やす
      等価 := 等価 + 1
    else  if A[eq] > pivot then 
      // 等しいか大きいインデックスの要素を交換します
      swap A[eq] with A[gt]
       // 大きい方のインデックスを減らします
      gt := gt - 1
    else  // if A[eq] = pivot then
       // 等インデックスを増やす
      等価 := 等価 + 1
  
  // 小さいインデックスと大きいインデックスを返す
  return lt, gt

アルゴリズムpartitionは、中央のパーティションの最初の (「左端」) 項目と最後の (「右端」) 項目へのインデックスを返します。パーティションのその他の項目はすべてピボットと等しいため、ソートされます。したがって、パーティションの項目は への再帰呼び出しに含める必要はありませんquicksort。

このアルゴリズムにとって最適なケースは、すべての要素が等しい場合 (またはk ≪ n個の要素の小さなセットから選択された場合) です。すべての要素が等しい場合、修正されたクイックソートは空のサブ配列に対して 2 回の再帰呼び出しのみを実行し、線形時間で終了します (partitionサブルーチンが線形時間よりも長くかからないと仮定)。

セジウィックが提案し、実際に広く使用されている他の重要な最適化は次のとおりです。^{[18] [19]}

• 最大O (log n ) のスペースが使用されるようにするには、最初にパーティションの小さい側を再帰し、次に末尾呼び出しを使用してもう一方の側を再帰するか、パラメーターを更新して、現在ソートされている小さい側を含めないようにし、大きい側をソートするように繰り返します。
• 要素数がしきい値 (たとえば 10 要素) を下回る場合は、そのような小さな配列に対してスワップ、比較、またはその他の操作をより少なく実行する挿入ソートなどの非再帰ソート アルゴリズムに切り替えます。理想的な「しきい値」は、特定の実装の詳細によって異なります。
• 以前の最適化の古いバージョン: 要素数がしきい値kより少ない場合は、単に停止します。配列全体が処理された後、挿入ソートを実行します。再帰を早期に停止すると、配列はkソートされたままになります。つまり、各要素は最終的なソート位置から最大でk位置離れています。この場合、挿入ソートはソートを完了するのにO ( kn )時間かかります。これは、 kが定数の場合は線形です。^{[20] [12] : 117} 「多数の小さなソート」の最適化と比較すると、このバージョンでは命令の実行数が少なくなるかもしれませんが、現代のコンピューターのキャッシュメモリを最適に使用しません。^[21]

クイックソートの分割統治法による定式化により、タスク並列処理を使用した並列化が可能になります。分割ステップは、分割された配列のセクション内の各配列要素のインデックスを計算する並列プレフィックス合計アルゴリズムを使用して実行されます。 ^{[22] [23]サイズ}nの配列が与えられた場合、分割ステップではO( n ) の作業をO (logn )時間で実行し、O( n )の追加スクラッチスペースが必要になります。配列が分割された後、2 つのパーティションを並列で再帰的にソートできます。ピボットの理想的な選択を前提とすると、並列クイックソートはサイズnの配列をO( n logn )の作業でソートし、 O(log2n ⁾時間でO( n )の追加スペースを使用します。

クイックソートには、マージソートなどの代替ソートアルゴリズムと比較するといくつかの欠点があり、効率的な並列化が複雑になります。クイックソートの分割統治ツリーの深さは、アルゴリズムのスケーラビリティに直接影響し、この深さはアルゴリズムのピボットの選択に大きく依存します。さらに、パーティショニング手順をインプレースで効率的に並列化することは困難です。スクラッチスペースを使用すると、パーティショニング手順は簡素化されますが、アルゴリズムのメモリフットプリントと一定のオーバーヘッドが増加します。

より洗練された他の並列ソートアルゴリズムでは、さらに優れた時間制限を達成することができます。[ ^24]たとえば、1991年にDavid MW Powersは、暗黙的にパーティショニングを実行することで、 n個のプロセッサを備えたCRCW（同時読み取りおよび同時書き込み）PRAM（並列ランダムアクセスマシン）でO（log n）時間で動作できる並列化クイックソート（および関連する基数ソート）を説明しました。^[25]

最も不均衡な分割は、分割ルーチンによって返されるサブリストの1つのサイズがn − 1である場合に発生します。^[26]これは、ピボットがリスト内の最小または最大の要素である場合、または一部の実装（たとえば、上記のLomuto分割スキーム）ではすべての要素が等しい場合に発生する可能性があります。

これがすべてのパーティションで繰り返し発生する場合、各再帰呼び出しは、前のリストよりもサイズが 1 小さいリストを処理します。その結果、サイズ 1 のリストに到達する前に、n − 1のネストされた呼び出しを行うことができます。これは、呼び出しツリーがn − 1のネストされた呼び出しの線形チェーンであることを意味します。i番目の呼び出しは、パーティションを実行するためにO ( n − i )の作業を実行し、その場合、クイックソートにはO ( n ² )の時間がかかります。 ${\displaystyle \textstyle \sum _{i=0}^{n}(ni)=O(n^{2})}$

最もバランスの取れたケースでは、パーティションを実行するたびに、リストをほぼ等しい 2 つの部分に分割します。つまり、各再帰呼び出しでは、サイズが半分のリストが処理されます。その結果、サイズ 1 のリストに到達するまでに、 log ₂ n 回のネストされた呼び出ししか実行できません。つまり、呼び出しツリーの深さはlog ₂ nです。ただし、呼び出しツリーの同じレベルの 2 つの呼び出しで、元のリストと同じ部分が処理されることはありません。そのため、各レベルの呼び出しに必要な時間は合計でO ( n )時間だけです (各呼び出しには一定のオーバーヘッドがありますが、各レベルでO ( n )回の呼び出ししかないため、これはO ( n )係数に含まれます)。結果として、アルゴリズムが使用する時間はO ( n log n )時間だけになります。

n個の異なる要素を持つ配列をソートする場合、クイックソートでは、等確率でn個の要素を持つn !個の順列すべてにわたって平均すると、期待値でO ( n log n ) の時間がかかります。あるいは、アルゴリズムが入力配列からピボットを均一にランダムに選択する場合、同じ分析を使用して、任意の入力シーケンスの期待実行時間を制限できます。その場合、期待値はアルゴリズムによって行われたランダムな選択に適用されます (Cormenら、「アルゴリズム入門」、^[13]セクション 7.3)。

ここでは、クイックソートの仕組みに関するさまざまな洞察を提供する、この主張に対する 3 つの一般的な証明を示します。

各ピボットのランクが中央の 50 パーセント、つまり 25パーセンタイルと 75 パーセンタイルの間であれば、両側に少なくとも 25 パーセント、最大で 75 パーセントの要素を分割します。このようなピボットを一貫して選択できれば、サイズ 1 のリストに到達するまでにリストを最大 回分割するだけで済み、 O ( n log n )アルゴリズムが得られます。 ${\displaystyle \log_{4/3}n}$

入力がランダム順列の場合、ピボットのランクはランダムであるため、中央 50 パーセント内にあることは保証されません。ただし、ランダム順列から開始すると、各再帰呼び出しでピボットのリストにランダムなランクが含まれるため、約半分の確率で中央 50 パーセント内になります。これで十分です。コインを投げると想像してください。表はピボットのランクが中央 50 パーセント内にあることを意味し、裏はそうでないことを意味します。次に、コインがk回表になるまで何度も投げられると想像してください。これには長い時間がかかる可能性がありますが、平均して2 k回投げるだけで済み、 100 k回投げた後にコインがk回表にならない可能性は非常に低いです (これはチェルノフ境界を使用して厳密にすることができます)。同じ議論により、クイックソートの再帰は平均して の呼び出し深度で終了します。しかし、平均呼び出し深度がO (log n )で、呼び出しツリーの各レベルが最大でn個の要素を処理する場合、平均して行われる作業量の合計は積O ( n log n )になります。アルゴリズムでは、ピボットが中央の半分にあることを確認する必要はありません。一定の割合でピボットに到達すれば、必要な複雑さには十分です。 ${\displaystyle 2\log_{4/3}n}$

代替アプローチは、サイズnのリストをソートするのに必要な時間であるT ( n )因子の再帰関係を設定することです。最も不均衡なケースでは、1回のクイックソート呼び出しにO ( n )の作業と、サイズ0とn −1のリストに対する2回の再帰呼び出しが含まれるため、再帰関係は次のようになります。

${\displaystyle T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).}$

これは挿入ソートや選択ソートの場合と同じ関係であり^、最悪の場合T ( n ) = O ( n2 )となります。

最もバランスのとれたケースでは、1回のクイックソート呼び出しにO ( n )の作業と、サイズn /2のリストに対する2回の再帰呼び出しが含まれるため、再帰関係は次のようになります。

${\displaystyle T(n)=O(n)+2T\left({\frac {n}{2}}\right).}$

分割統治法のマスター定理によれば、 T ( n ) = O ( n log n )となります。

O ( n log n )の期待時間計算量の正式な証明の概要は次のとおりです。重複は線形時間の前処理と後処理で処理できるか、分析したケースよりも簡単であると考えられるため、重複は存在しないものとします。入力がランダム順列の場合、ピボットのランクは 0 からn − 1までの一様ランダムです。その結果得られるパーティションの各部分のサイズはiとn − i − 1で、 i は 0 からn − 1までの一様ランダムです。したがって、すべての可能な分割を平均し、パーティションの比較回数がn − 1であることに注目すると、入力シーケンスのすべての順列の平均比較回数は、再帰関係を解くことで正確に推定できます。

${\displaystyle C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(ni-1))=n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)}$

${\displaystyle nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)}$

${\displaystyle nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)}$

${\displaystyle nC(n)=(n+1)C(n-1)+2n-2}$

${\displaystyle {\begin{aligned}{\frac {C(n)}{n+1}}&={\frac {C(n-1)}{n}}+{\frac {2}{n+1}}-{\frac {2}{n(n+1)}}\leq {\frac {C(n-1)}{n}}+{\frac {2}{n+1}}\\&={\frac {C(n-2)}{n-1}}+{\frac {2}{n}}-{\frac {2}{(n-1)n}}+{\frac {2}{n+1}}\leq {\frac {C(n-2)}{n-1}}+{\frac {2}{n}}+{\frac {2}{n+1}}\\&\ \ \vdots \\&={\frac {C(1)}{2}}+\sum _{i=2}^{n}{\frac {2}{i+1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\approx 2\int _{1}^{n}{\frac {1}{x}}\mathrm {d} x=2\ln n\end{aligned}}}$

再帰式を解くと、C ( n ) = 2 n ln n ≈ 1.39 n log ₂ nとなります。

これは、平均すると、クイックソートのパフォーマンスは最良の場合よりも約 39% しか低下しないことを意味します。この意味では、クイックソートは最悪の場合よりも最良の場合に近いと言えます。比較ソートでは、 n個の項目をソートするのに平均してlog ₂ ( n !)回未満の比較を使用することはできません( 「比較ソート」の記事で説明されているように)。また、 nが大きい場合、スターリングの近似によりlog ₂ ( n !) ≈ n (log ₂ n − log ₂ e )となるため、クイックソートは理想的な比較ソートと比べてそれほど劣っていません。この平均実行時間の短さは、クイックソートが他のソート アルゴリズムよりも実質的に優れているもう 1 つの理由です。

次のバイナリ検索ツリー(BST) は、クイックソートの各実行に対応します。最初のピボットはルート ノードです。左半分のピボットは左サブツリーのルート、右半分のピボットは右サブツリーのルート、というように続きます。クイックソートの実行の比較回数は、挿入シーケンスによる BST の構築中の比較回数と同じです。したがって、ランダム化クイックソートの平均比較回数は、挿入された値がランダムな順列を形成する場合の BST 構築の平均コストと同じです。 ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$

ランダムな順列を形成する値のシーケンスを挿入することによって作成された BST を考えてみましょう。 C はBST の作成コストを表します。 となります。ここで、は の挿入中に との比較があったかどうかを表すバイナリランダム変数です。 ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$${\displaystyle C=\sum _{i}\sum _{j<i}c_{i,j}}$${\displaystyle c_{i,j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$

期待値の線形性により、 Cの期待値はです。 ${\displaystyle \operatorname {E} [C]}$${\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})}$

i を固定し、 j < iとします。値は、ソートされると、j +1区間を定義します。中核となる構造上の観察は、が に隣接する 2 つの区間のいずれかに含まれる場合にのみ、アルゴリズムで がと比較されるということです。 ${\displaystyle {x_{1},x_{2},\ldots ,x_{j}}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$

はランダムな順列なので、もランダムな順列であり、 がに隣接する確率はちょうど であることに注目してください。 ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$${\displaystyle (x_{1},x_{2},\ldots ,x_{j},x_{i})}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle {\frac {2}{j+1}}}$

最後に簡単な計算をします。

${\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\log i\right)=O(n\log n).}$

クイックソートによって使用されるスペースは、使用されるバージョンによって異なります。

クイックソートのインプレースバージョンは、以下の戦略を使用して慎重に実装すると、最悪の場合でも 空間計算量はO (log n )になります。

• インプレースパーティショニングが使用されます。この不安定なパーティションにはO (1)のスペースが必要です。
• パーティション分割後、要素数が最も少ないパーティションが最初に（再帰的に）ソートされ、最大でもO (log n )のスペースしか必要としません。次に、もう一方のパーティションが末尾再帰または反復を使用してソートされます。これにより、呼び出しスタックは増加しません。このアイデアは、上で説明したように、R. Sedgewickによって説明され、スタックの深さをO (log n )に制限します。^{[17] [20]}

インプレースおよび不安定なパーティショニングを使用したクイックソートでは、再帰呼び出しを行う前に一定の追加スペースのみが使用されます。クイックソートでは、ネストされた再帰呼び出しごとに一定量の情報を保存する必要があります。最良のケースでは最大でO (log n )のネストされた再帰呼び出しが行われるため、O (log n ) のスペースが使用されます。ただし、再帰呼び出しを制限する Sedgewick のトリックがなければ、最悪のケースではクイックソートでO ( n ) のネストされた再帰呼び出しが行われ、O ( n )の補助スペースが必要になる可能性があります。

ビットの複雑さの観点から見ると、 loやhiなどの変数は定数のスペースを使用しません。n 個の項目のリストにインデックスを付けるには O (log n ) ビットが必要です。このような変数はすべてのスタック フレームに存在するため、Sedgewick のトリックを使用したクイックソートにはO ((log n ) ² )ビットのスペースが必要です。ただし、このスペース要件はそれほどひどいものではありません。リストに異なる要素が含まれている場合、少なくともO ( n log n )ビットのスペースが必要になるためです。

クイックソートのもう 1 つのバージョンは、あまり一般的ではない非インプレース バージョンで、作業用ストレージにO ( n )スペースを使用し、安定したソートを実装できます。作業用ストレージにより、入力配列を安定した方法で簡単に分割し、その後、後続の再帰呼び出しのために入力配列にコピーし直すことができます。Sedgewick の最適化は依然として適切です。

クイックソートは、バイナリ ツリー ソートのスペース最適化バージョンです。明示的なツリーに項目を順番に挿入する代わりに、クイックソートは、再帰呼び出しによって暗示されるツリーに項目を同時に整理します。これらのアルゴリズムは、まったく同じ比較を異なる順序で行います。ソート アルゴリズムの望ましい特性として、安定性が挙げられます。つまり、等しいと判断される要素の順序は変更されず、マルチキー テーブル (ディレクトリまたはフォルダーの一覧など) の順序を自然な方法で制御できます。この特性は、インプレース クイックソート (ポインターとバッファー用に一定の追加スペースのみを使用し、明示的または暗黙的な再帰の管理用にO (log n )の追加スペースのみを使用する) では維持が困難です。ポインター (リストやツリーなど) またはファイル (実質的にはリスト) を使用した表現のために余分なメモリを必要とするバリアント クイックソートでは、安定性を維持するのは簡単です。より複雑な、またはディスクにバインドされたデータ構造は、時間コストが増加する傾向があり、一般に仮想メモリまたはディスクの使用が増えます。

クイックソートの最も直接的な競合相手はヒープソートである。ヒープソートは単純さや、最悪実行時間がO ( n log n )という利点があるが、ヒープソートの平均実行時間は、主に参照の局所性が悪いために、通常、インプレースクイックソートよりも遅いと考えられている。^[27]この結果は議論の余地があり、反対のことを示唆する出版物もある。^{[28] [29]}クイックソートの主な欠点は、不適切なピボット選択を回避するために必要な実装の複雑さと、その結果生じるO ( n ² )のパフォーマンスである。 イントロソートはクイックソートの変種であり、不適切なケースが検出されるとヒープソートに切り替えることでこの問題を解決する。C++ (GNU および LLVM 実装) などの主要なプログラミング言語は、イントロソートを使用する。^[30]

クイックソートは、別のO ( n log n )ソートアルゴリズムであるマージソートとも競合します。マージソートの主な利点は、安定したソートであり、最悪ケースのパフォーマンスが優れていることです。マージソートの主な欠点は、アウトオブプレースアルゴリズムであるため、配列を操作するときに効率的な実装にO ( n ) の補助スペースが必要になることです (インプレースパーティショニングと末尾再帰を使用したクイックソートの場合はO (log n ) 、ヒープソートの場合はO (1)です)。

マージ ソートはリンク リストで非常にうまく機能し、少量の一定量の補助ストレージのみを必要とします。クイック ソートはリンク リストを使用して安定したソートとして実装できますが、そうする理由はありません。クイック ソートはランダム アクセスなしでは不適切なピボット選択に悩まされることが多く、本質的にマージ ソートよりも常に劣ります。マージ ソートは、ディスク ストレージやネットワーク接続ストレージなどのアクセスが遅いメディアに保存された非常に大きなデータ セットの外部ソートにも選択されるアルゴリズムです。

2 つのバケットを使用したバケット ソートはクイックソートに非常に似ています。この場合のピボットは実質的に値の範囲の中央の値であり、均一に分散された入力に対して平均的に良好なパフォーマンスを発揮します。

選択アルゴリズムは、数値のリストのk番目に小さいものを選択します。これは一般にソートよりも簡単な問題です。 1 つのシンプルだが効果的な選択アルゴリズムは、クイックソートとほぼ同じように動作するため、クイックセレクトと呼ばれます。違いは、両方のサブリストで再帰呼び出しを行うのではなく、目的の要素を含むサブリストで 1 回の末尾再帰呼び出しのみを行うことです。この変更により、平均複雑度が線形またはO ( n )時間に低下し、選択には最適ですが、選択アルゴリズムは最悪の場合でも O ( n ² )のままです。

クイックセレクトのバリエーションである中央値の中央アルゴリズムは、ピボットをより慎重に選択し、ピボットがデータの中央付近（30 パーセンタイルと 70 パーセンタイルの間）にあることを保証し、線形時間（O ( n ) ）を保証します。この同じピボット戦略を使用して、クイックソートのバリエーション（中央値の中央クイックソート）をO ( n log n )時間で構築できます。ただし、ピボットを選択するオーバーヘッドが大きいため、これは通常、実際には使用されません。

より抽象的に言えば、O ( n )選択アルゴリズムが与えられれば、それを使用してクイックソートの各ステップで理想的なピボット (中央値) を見つけることができ、実行時間がO ( nlogn )のソートアルゴリズムを生成できます。このバリアントの実際の実装は平均してかなり遅くなりますが、最適な選択アルゴリズムが最適なソートアルゴリズムを生み出すことができることを示しているため、理論的には興味深いものです。

マルチピボットクイックソート（マルチクイックソート^{[21]とも呼ばれる）は、単一のピボットを使用して2つのサブ配列に分割する代わりに、} s − 1個のピボットを使用して入力をs個のサブ配列に分割します。デュアルピボットの場合（s = 3）は、1970年代半ばにすでにセジウィックらによって検討されていましたが、結果として得られたアルゴリズムは実際には「古典的な」クイックソートよりも高速ではありませんでした。^[31]プロセッサキャッシュを効率的に使用するために調整された可変数のピボットを備えたマルチクイックソートの1999年の評価では、命令数が約20％増加することがわかりましたが、シミュレーション結果から、非常に大きな入力ではより効率的であることが示唆されました。^[21] 2009年にYaroslavskiyによって開発されたデュアルピボットクイックソートのバージョン^[32]は、プリミティブ配列をソートする標準アルゴリズムとしてJava 7に実装されるのに十分なほど高速であることが判明しました（オブジェクトの配列のソートはTimsortを使用して行われます）。^[34]このアルゴリズムのパフォーマンス上の利点は、主にキャッシュパフォーマンスに関連していることが判明し、^[35]実験結果では、3ピボットバリアントは最新のマシンでさらに優れたパフォーマンスを発揮する可能性があることが示されています。^{[36] [37]}

ディスク ファイルの場合、クイックソートに似たパーティション分割に基づく外部ソートが可能です。外部マージ ソートよりも低速ですが、余分なディスク領域は必要ありません。4 つのバッファーが使用されます (2 つは入力用、2 つは出力用)。ファイル内のレコード数、バッファーあたりのレコード数、およびファイル内のバッファー セグメント数とします。データはファイルの両端から内側に向​​かって読み取られ (および書き込まれ) ます。はファイルの先頭から始まるセグメントを表し、はファイルの末尾から始まるセグメントを表します。データは読み取りバッファーと読み取りバッファーに読み込まれます。ピボット レコードが選択され、ピボット レコード以外のバッファーとバッファー内のレコードは、ピボット レコードとの比較に基づいて昇順で書き込みバッファーにコピーされ、降順で書き込みバッファーにコピーされます。いずれかのバッファーまたはバッファーがいっぱいになると、ファイルに書き込まれ、次のバッファーまたはバッファーがファイルから読み取られます。すべてのセグメントが読み取られ、1 つの書き込みバッファーが残るまで、このプロセスが続行されます。そのバッファーが書き込みバッファーの場合、ピボット レコードがそのバッファーに追加され、バッファーが書き込まれます。そのバッファが書き込みバッファの場合、ピボットレコードがバッファの先頭に追加され、バッファが書き込まれます。これはファイルの 1 つのパーティションステップを構成し、ファイルは 2 つのサブファイルで構成されるようになります。各サブファイルの開始位置と終了位置は、再帰によってスタンドアロンスタックまたはメインスタックにプッシュ/ポップされます。スタックスペースを に制限するために、小さい方のサブファイルが最初に処理されます。スタンドアロンスタックの場合は、大きい方のサブファイルパラメータをスタックにプッシュし、小さい方のサブファイルで繰り返し処理します。再帰の場合は、小さい方のサブファイルを最初に再帰処理し、次に大きい方のサブファイルを処理するために繰り返し処理します。サブファイルが 4 B レコード以下になると、サブファイルはクイックソートによってインプレースでソートされ、書き込まれます。そのサブファイルは、ファイル内でソートされ、インプレースで配置されます。このプロセスは、すべてのサブファイルがソートされ、インプレースで配置されるまで続けられます。ファイルの平均パス数は約 ですが、最悪の場合のパターンはパスです (最悪の場合の内部ソートでは に相当します)。^[38]${\displaystyle N=}$${\displaystyle B=}$${\displaystyle M=N/B=}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle O(\log _{2}(n))}$${\displaystyle {\frac {1+\ln(N+1)}{(4B)}}}$${\displaystyle N}$${\displaystyle O(n^{2})}$

このアルゴリズムは、基数ソートとクイックソートを組み合わせたものです。配列 (ピボット) から要素を 1 つ選択し、文字列 (マルチキー) の最初の文字 (キー) を検討します。残りの要素を、対応する文字がピボットの文字より小さい、等しい、大きいという 3 つのセットに分割します。「小さい」および「大きい」パーティションを同じ文字で再帰的にソートします。「等しい」パーティションを次の文字 (キー) で再帰的にソートします。長さWビットのバイトまたはワードを使用してソートする場合、最良のケースはO ( KN )、最悪のケースはO (2 ^K N )、または少なくとも標準のクイックソートの場合のO ( N ² )です (一意のキーN <2 ^Kの場合) 。Kは、クイックソートを含むすべての標準の比較ソートアルゴリズムで隠れた定数です。これは、中央のパーティションがピボットと 正確に等しい要素の (自明な) ソート済みサブ配列を表す、3 方向クイックソートの一種です。

Powers によってO ( K )並列PRAMアルゴリズムとしても開発されました。これも基数ソートとクイックソートの組み合わせですが、クイックソートの左/右パーティションの決定はキーの連続するビットに対して行われるため、N Kビットのキーに対してO ( KN )になります。すべての比較ソートアルゴリズムは、 KがΘ (log N )のトランス二分モデルを暗黙的に想定しています。つまり、 Kが小さい場合は、ハッシュ テーブルまたは整数ソートを使用してO ( N )時間でソートできます。K ≫ log Nであっても、要素がO (log N )ビット以内で一意である場合、残りのビットはクイックソートまたはクイック基数ソートのいずれでも参照されません。それができない場合、すべての比較ソートアルゴリズムは、比較的役に立たないO ( K )ビット^を調べるという同じオーバーヘッドを持つことになりますが、クイック基数ソートは、標準クイックソートと基数クイックソートの最悪のケースであるO ( N2 )の動作を回避し、 uniqueprefix( K )≫logNの条件下では、これらの比較アルゴリズムの最良のケースでも高速になります。比較、基数、並列ソートの隠れたオーバーヘッドの詳細については、 Powers ^{[39]を参照してください。}

比較ベースのソートアルゴリズムでは、比較回数を最小限に抑えるには、各比較から得られる情報の量を最大化する必要があり、比較結果は予測不可能になります。これにより、分岐の予測ミスが頻繁に発生し、パフォーマンスが制限されます。^[40] BlockQuicksort ^[41]は、クイックソートの計算を再配置して、予測不可能な分岐をデータ依存関係に変換します。分割する際、入力は中程度のサイズのブロック(データキャッシュに簡単に収まる) に分割され、2 つの配列にスワップする要素の位置が格納されます。(条件分岐を回避するために、位置は無条件に配列の最後に格納され、スワップが必要な場合は末尾のインデックスが増分されます。) 2 回目のパスでは、配列で示された位置の要素が交換されます。両方のループには、通常は実行される終了テストという条件分岐が 1 つだけあります。

BlockQuicksort技術はLLVMのC++ STL実装libcxxに組み込まれており、ランダム整数シーケンスの50%の改善を実現しています。introsortの一種であるパターンディフィートクイックソート（pdqsort）にもこの技術が組み込まれています。^[30]

クイックソートには、 k個の最小または最大の要素を残りの入力から 分離するバリエーションがいくつかあります。

リチャード・コールとデイビッド・C・カンダシルは2004年に、パーティションソートと呼ばれる1パラメータのソートアルゴリズム群を発見した。これは平均すると（すべての入力順序が等しく起こり得る場合）、多くても比較（情報理論の下限に近い）と演算を実行し、最悪の場合でも比較（および演算）を実行する。これらはインプレースであり、必要なのは追加のスペースのみである。実用的な効率性とパフォーマンスのばらつきの少なさは、セジウィックとベントレー・マキロイによる最適化されたクイックソートに対して実証された。^[42]${\displaystyle n\log n+{O}(n)}$${\displaystyle {\Theta }(n\log n)}$${\displaystyle {\Theta }(n\log ^{2}n)}$${\displaystyle {O}(\log n)}$

• Introsort  – ハイブリッドソートアルゴリズム