クイックセレクト
始めはクイックセレクトを使って、ある程度の回数で終了しなかった場合に中央値の中央値を使うことで、高速の平均ケースパフォーマンスと線形の最悪ケースパフォーマンスの両方を達成できる。この手法を使うのがイントロセレクト(英語版)である。
平均時間計算量についてより細かく計算すると、少なくとも n ( 2 + 2 log  2 + o ( 1 ) ) ≤ 3.4 n + o ( n ) {\displaystyle n(2+2\log 2+o(1))\leq 3.4n+o(n)} 以下である(これは中央値の場合で、他のkの方が高速)。 フロイド・リベストのアルゴリズム(英語版)ではより複雑なピボット戦略によって 3/2 の改善を果たしている。この場合、 1.5 n + Θ ( n 1 / 2 ) {\displaystyle 1.5n+\Theta (n^{1/2})} となる(これは中央値の場合で、他のkの方が高速)。