選択アルゴリズム
一貫して良いピボット値を見つけることができれば、クイックセレクトを最悪でも線形時間にすることができる。そのためにまず、元の配列を5つずつの要素の小配列に分割する。次にその小配列ごとに中央値を探し、その各中央値だけを抽出した配列に対して、さらに選択アルゴリズムを再帰的に適用する。そうして見つかった中央値の中央値は、ピボット値として最適であり、1回の反復で元の配列の要素数より一定の割合(最善で3割、最悪でも7割)に減らすことができる。
ただし、この方法では最悪時間は確かに線形になるが、平均時間は、実際にはピボット値を無作為に選ぶなどの素朴な方式の方が優れている。