イントロソート

イントロソートまたはイントロスペクティブソートは、高速な平均パフォーマンスと（漸近的に）最適な最悪ケースのパフォーマンスの両方を提供するハイブリッド ソートアルゴリズムです。クイックソートから始まり、再帰の深さがソート対象の要素数（の対数）に基づくレベルを超えるとヒープソートに切り替わり、要素数が特定のしきい値を下回ると挿入ソートに切り替わります。これは、3つのアルゴリズムの良い部分を組み合わせたもので、一般的なデータセットではクイックソートに匹敵する実用的なパフォーマンスと、ヒープソートによる最悪ケースのO（n log n ）実行時間を実現します。使用する3つのアルゴリズムは比較ソートであるため、これも比較ソートです。

イントロソートは、 David Musserによって Musser (1997) で発明されました。この論文で彼は、クイックソートのバリエーションであるクイックセレクトに基づくハイブリッド選択アルゴリズムである introselect も導入しました。これは、中央値の中央値に戻るため、最悪の場合の線形複雑度が最適になります。両方のアルゴリズムは、平均パフォーマンスが速く、最悪の場合のパフォーマンスが最適である汎用アルゴリズムをC++ 標準ライブラリに提供することを目的として導入され、パフォーマンス要件を厳しくすることができました。^{[1]イントロソートは}インプレースで非安定なアルゴリズム です。

ヒープソートの実装とクイックソートの記事で説明したタイプの分割関数が利用できる場合、イントロソートは次のように簡潔に記述できます。

手順sort(A : 配列):
    最大深度 ← ⌊log 2 (長さ(A))⌋ × 2
    イントロソート(A, 最大深度)

手順introsort(A, maxdepth):
    n ← 長さ(A)
    n < 16の場合:
        挿入ソート(A)
    それ以外の場合、 maxdepth = 0 の場合:
        ヒープソート(A)
    それ以外：
        p ←partition(A)   // この関数はピボット選択を行うと仮定します。p はピボットの最終位置です。
        イントロソート(A[1:p-1], 最大深度 - 1)
        イントロソート(A[p+1:n], 最大深度 - 1)

最大深度の係数 2 は任意であり、実際のパフォーマンスに合わせて調整できます。A [ i : j ] は、 A [ i ]とA [ j ] の両方を含む項目iからjまでの配列スライスを表します。インデックスは 1 から始まるものと想定されます ( A配列の最初の要素はA[1]です)。

クイックソートでは、重要な操作の 1 つがピボット (リストを分割する要素) の選択です。最も単純なピボット選択アルゴリズムは、リストの最初または最後の要素をピボットとして選択することですが、ソート済みまたはほぼソート済みの入力の場合に動作が悪くなります。Niklaus Wirthのバリアントは、中央の要素を使用してこれらの発生を防ぎ、不自然なシーケンスの場合は O( n ² ) に縮退します。median-of-3 ピボット選択アルゴリズムは、リストの最初、中央、および最後の要素の中央値を選択します。ただし、これは多くの実際の入力で適切に機能しますが、このピボット選択手法に基づくクイックソートの速度を大幅に低下させる median-of-3 キラーリストを考案することは依然として可能です。

Musser は、100,000 要素の median-of-3 キラー シーケンスでは、イントロソートの実行時間は median-of-3 クイックソートの 1/200 だったと報告しています。Musser はまた、小さな範囲が挿入ソートの 1 回のパスで最後にソートされるSedgewickの遅延スモール ソートのキャッシュへの影響についても検討しました。Musser は、キャッシュ ミスの数が 2 倍になる可能性があるが、両端キューでのパフォーマンスが大幅に向上し、テンプレート ライブラリ用に保持する必要があると報告しました。これは、他のケースではソートをすぐに実行することによる利点が大きくなかったためです。

Introsort またはそのバリアントは、いくつかのC++ ソート実装を含む、多くの標準ライブラリソート関数で使用されます。

2000 年 6 月のSGI C++標準テンプレート ライブラリstl_algo.h の不安定ソートの実装では、ヒープソートに切り替えるための再帰深度をパラメータとして渡した Musser イントロソート アプローチ、中央値 3 のピボット選択、および 16 未満のパーティションに対する Knuth 最終挿入ソート パスを使用します。

GNU標準C++ライブラリも同様で、最大深度2×log ₂ nのイントロソートを使用し、続いて16未満のパーティションで挿入ソートを実行します^。[2]

LLVM libc++も最大深度2×log ₂ nのイントロソートを使用しますが、挿入ソートのサイズ制限はデータ型によって異なります（スワップが簡単な場合は30、そうでない場合は6）。また、サイズが5までの配列は個別に処理されます。^[3] Kutenin（2022）は、2022年の二次性修正に焦点を当てて、LLVMによるいくつかの変更の概要を示しています。^[4]

Microsoft .NET Framework クラスライブラリは、バージョン4.5（2012）以降、単純なクイックソートの代わりにイントロソートを使用しています。^[5]

Goはイントロソートの修正版を使用します。12要素以下のスライスには挿入ソートを使用し、より大きなスライスにはパターンを無視したクイックソートと、より高度な3つの中央値の中央値を使用してピボットを選択します。^[6]バージョン1.19より前は、小さなスライスにはシェルソートを使用していました。

Javaはバージョン14（2020年）以降、高度に構造化された配列（少数のソートされたサブ配列で構成される配列）にはマージソートを使用し、それ以外の場合はint、long、float、doubleの配列をソートするためにイントロソートを使用するハイブリッドソートアルゴリズムを使用します。^[7]

パターンディフィートクイックソート（pdqsort）は、以下の改良を組み込んだイントロソートの変種である：^[8]

• 3つの中央値ピボット、
• 分岐予測ミスのペナルティを軽減する「BlockQuicksort」分割技術
• 特定の入力パターンに対する線形時間パフォーマンス（適応ソート）、
• より遅いヒープソートを試す前に、悪いケースでは要素のシャッフルを使用します。
• 低カーディナリティ入力に対する適応性の向上

pdqsortはRust、GAP、^[9]、C++ライブラリBoostで使用されています。^[10]

fluxsortはintrosortの安定した変種であり、以下の改良が組み込まれている: ^[11]

• 分岐なしsqrt(n)ピボット
• 安定した部分的インプレース分割のためのフラックス分割技術
• 分岐のない双方向パリティマージを利用することで、スモールソートを大幅に改善しました。
• 分岐のない双方向マージソートであるクワッドソートへのフォールバックにより、順序付けられた入力に対する適応性が大幅に向上します。

fluxsortとその不安定な変種であるcrumsortによって導入された改良は、crumsort-rs、glidesort、ipnsort、driftsortに採用されました。pdqsortと比較したランダム入力での全体的なパフォーマンスの向上は約50％です。^{[12] [13] [14] [15] [16]}