最悪時間となる場合は、例えば、各段階でピボット値として最小値を選んでしまう時である。これは、既に降順に並べ替え済みの配列に対して、最初の要素をピボット値として選択してしまうと実際に起こりうる。つまり、もし各段階で一貫して「良いピボット値」を選択し続けられるなら、このような最悪の場合を回避することができ、最悪の場合でも線形時間の性能となる。この「良いピボット値」では、全ての要素を一定の割合でより大きい値と小さい値に分割することができ、つまり探索対象の要素数を一定の割合で減らすことができ、ゆえに要素数が指数関数的に減少して、全体的な計算時間は線形のままとなる。中央値は、そのような「良いピボット値」であり、各段階で探索対象を半分ずつに減らすことができる。ゆえに、もし中央値を線形時間で計算できるなら、各段階では線形時間しか増えないので、全体の計算量は線形時間のままとなる。計算手法.前述のように、中央値の中央値はクイックセレクトのピボット値選択で用いられる。クイックセレクトを擬似コードで書くと以下のようになる。//ピボット値を計算する//領域を分割して、ピボット値の位置を計算する//次の探索開始地点はピボット値の右隣から//次の探索終了地点はピボット値の左隣まで先述の通り、このに中央値の中央値を適用すると、計算される値が全体の配列のおおよその中央値となる。具体的には以下の手順で計算できる。//小配列の開始地点と終了地点//結果を格納する//各小配列の中央値を集めた配列の中で、さらに中央値を計算する(中央値の中央値)このように、はを呼び出しており相互再帰となっている。ピボット値の特性.中央値の中央値をピボット値として採用すると、ピボット値は以下の様な特性を持つ。ここで、背景がである。処理時間が線形であることの証明.だからである。ここで小配列への分割方法.クイックソートにおける中央値の中央値.イントロセレクト.中央値の中央値は、の中でも使用される。イントロセレクトでは、最初はクイックセレクトで計算することで平均計算時間を改善し、もし処理に時間が掛かりそうな場合は中央値の中央値に切り替えることで最悪計算時間も線形に抑えることができる。ゴードン公爵ゴードン公爵()は、イギリスの公爵位。歴史.