title: Understanding "median of medians" algorithm
body: <p>I want to understand "median of medians" algorithm on the following example:</p>
  
  <p>We have 45 distinct numbers divided into 9 group with 5 elements each.</p>
  
  <pre><code>48 43 38 33 28 23 18 13 8
  
  49 44 39 34 29 24 19 14 9 
  
  50 45 40 35 30 25 20 15 10
  
  51 46 41 36 31 26 21 16 53
  
  52 47 42 37 32 27 22 17 54
  </code></pre>
  
  <ol>
  <li>The first step is sorting every group (in this case they are already sorted)</li>
  <li><p>Second step recursively, ﬁnd the "true" median of the medians (<code>50 45 40 35 30 25 20 15 10</code>) i.e. the set will be divided into 2 groups:</p>
  
  <pre><code>50 25
  
  45 20 
  
  40 15
  
  35 10
  
  30
  </code></pre>
  
  <p>sorting these 2 groups</p>
  
  <pre><code>30 10
  
  35 15 
  
  40 20
  
  45 25
  
  50
  </code></pre></li>
  </ol>
  
  <p>the medians is 40 and 15 (in case the numbers are even we took left median)
  so the returned value is 15 however "true" median of medians (<code>50 45 40 35 30 25 20 15 10</code>) is 30, moreover there are 5 elements less then 15 which are much less than 30% of 45 which are mentioned in <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear%5Fgeneral%5Fselection%5Falgorithm%5F-%5F.22Median%5Fof%5FMedians%5Falgorithm.22">wikipedia</a></p>
  
  <p>and so <code>T(n) &lt;= T(n/5) + T(7n/10) + O(n)</code> fails.</p>
  
  <p>By the way in the Wikipedia example, I get result of recursion as 36. However, the true median is 47.</p>
  
  <p>So, I think in some cases this recursion may not return true median of medians. I want to understand where is my mistake.     </p>