イントロソート

イントロソート（英: introsort）は、 が1997年に設計した、クイックソートとヒープソートを組み合わせたソートアルゴリズムである。 最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。時間計算量は最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。 イントロソートは、クイックソートやヒープソートと同様、である。 クイックソートは、性能がピボット（データ列を分割する境界値）の選択に強く依存するという欠点があった。例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。ニクラウス・ヴィルトはこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては最悪で O(n2) となる。よりロバストな方法として先頭、最後尾、中央の値の中央値をピボットに選ぶアルゴリズム（median-of-3 pivot）もある。大抵のデータ列のソートはこれでほとんどうまくいくが、データ列を工夫することで性能を大幅に低下させることができ、DoS攻撃に利用できる。 Musser は、median-of-3 pivot クイックソートが最悪値を示すようなデータであっても、例えば要素数 100000 のデータに対してイントロソートの実行時間がクイックソートの 1/200 になったことを報告している。 Musser は Robert Sedgewick が考案したキャッシュメモリの効果を考慮したソートアルゴリズムも検討した。それは、細かい部分について挿入ソートを1回最後に行うというものである。彼によると、イントロソートではキャッシュミス率は2倍になるが、両端キューを使った実装では劇的に性能を改善できるため、テンプレートライブラリに保持すべきだとしている（特に、キャッシュの保持されている間にソートを行わないこともあるため）。 クイックソートと同様の考えを適用した選択アルゴリズムとして、アントニー・ホーアのクイックセレクトがある。選択アルゴリズムも同様にイントロソートの考えを適用でき、の計算量は、最悪時間でも線形時間となる（クイックセレクトの最悪時間は O(n2)）。 2000年6月、SGI C++ Standard Template Library で、Musser のイントロソートの手法を利用した不安定ソートの実装をした。ヒープソートに切り替える再帰の深さは引数で指定でき、最終段は Sedgewick の挿入ソートを使う方式である。挿入ソートに切り替わる再帰の深さは16だった。