Median of mediansのアプローチは、かなり良いピボットをもたらすために、quicksortタイプの分割アルゴリズムで非常に普及しており、アレイを一様に分割します。その論理はウィキペディアで次のように与えられます：メディアンの中央値の説明アルゴリズム
選択されたピボットは、メジアンのリストの要素の半分よりも小さく、n/10要素（1/2 *（n/5） ））。これらの要素のそれぞれは5の中央値であり、2つ未満の他の要素とブロック外の2つ以上の他の要素となります。したがって、ピボットはブロック外の3（n/10）個未満であり、ブロック外の3（n/10）個以上の要素です。したがって、選択された中央値は、アルゴリズムの最悪の場合の線形動作を保証する、30％/ 70％〜70％/ 30％の間のどこかの要素を分割する。
誰かが私にとって明快に説明できますか？私はその論理を理解するのが難しいと思っています。数字の次のセットの
思う：
5 2 6 3 1
これらの数字の中央値は3です。数字nがある場合、n > 3の場合は、上記の数字の半分以上です。 n < 3の場合、上記の数字の少なくとも半分よりも小さくなります。
これはその考えです。つまり、5つの数値の各セットについて、その中央値を取得します。今あなたはn/5の番号を持っています。これは明らかです。
これらの数値の中央値を取得すると（mと呼ぶ）、それらの半分より大きく、他の半分よりも小さい（中央値の定義によって！）。換言すれば、mはn/10（それ自体が小5元素グループの中央値）より大きく、別のn/10数字（小元素グループの中央値でもある）よりも大きい。上記の例では
、私たちは、中央値がkであり、あなたがm > kを持っている場合、その後、mも（kより小さい自身だった）2つの他の数字よりも大きいことがわかりました。これは、mがその媒体よりも大きいそれらのより小さい5つの要素グループのそれぞれについて、mが2つの他の数よりも大きいことを意味する。これにより、n/10小要素グループのそれぞれに少なくとも3つの数字（2つの数字+中央値自体）があり、それはmより小さい。したがって、mは少なくとも3n/10より大きい数値です。
要素数の類似したロジックは、mより大きい。
中央値の説明 - の - n個のうちk番目の最大の整数がまたここに見つけることができる見つけるために中央値アルゴリズム：http://cs.indstate.edu/~spitla/presentation.pdf
このメソッドは、この数は中央値であることを保証するんかちょうど別の質問、 ？中央値は、配列を上半分と下半分に分割する数値です。それで30-30-70の数字は何を表していますか？ – SexyBeast
まあ、中央値は中央にありますが、 'm'（上のテキスト）はすべての数値の中央値ではありません。それは数字のわずか5分の1の中央値である（それは小さな5要素グループの中央値である）。もっと注意を払って最後の段落を読んでみてください。結局、「m」が少なくとも「3n/10」よりも大きいと結論づけられたところでは、「m」は少なくとも30％よりも大きいと解釈されます。結局、それは「m」が少なくとも30％より大きく、少なくとももう30％より小さくなるようになります。私たちは確信が持てません40％が残っています。 – Shahbaz
それでは平均して50-50パーティションになるのはどうですか？ 50-50パーティションは正規の中央値で与えられます。 – SexyBeast