イントロソート
イントロソート(英: introsort)は、David Musser(英語版) が1997年に設計した、クイックソートとヒープソートを組み合わせたソートアルゴリズムである。
最初はクイックソートを行い、再帰のレベルがソートされた要素数(の対数)を超えるとヒープソートに切り替える。時間計算量は最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。
イントロソートは、クイックソートやヒープソートと同様、比較ソートである。
クイックソートは、性能がピボット(データ列を分割する境界値)の選択に強く依存するという欠点があった。 例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。 ニクラウス・ヴィルトはこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては最悪で O(n) となる。 よりロバストな方法として先頭、最後尾、中央の値の中央値をピボットに選ぶアルゴリズム(median-of-3 pivot)もある。大抵のデータ列のソートはこれでほとんどうまくいくが、データ列を工夫することで性能を大幅に低下させることができ、DoS攻撃に利用できる。