I want to understand &quot;median of medians&quot; algorithm on the following example:

We have 45 distinct numbers divided into 9 group with 5 elements each.

    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

1. The first step is sorting every group (in this case they are already sorted)
2. Second step recursively, ﬁnd the &quot;true&quot; median of the medians (`50 45 40 35 30 25 20 15 10`) i.e. the set will be divided into 2 groups:

        50 25
            
        45 20 
             
        40 15
    
        35 10
    
        30

  sorting these 2 groups


        30 10
            
        35 15 
             
        40 20
    
        45 25
    
        50

the medians is 40 and 15 (in case the numbers are even we took left median)
so the returned value is 15 however &quot;true&quot; median of medians (`50 45 40 35 30 25 20 15 10`) is 30, moreover there are 5 elements less then 15 which are much less than 30% of 45 which are mentioned in [wikipedia](http://en.wikipedia.org/wiki/Selection_algorithm#Linear%5Fgeneral%5Fselection%5Falgorithm%5F-%5F.22Median%5Fof%5FMedians%5Falgorithm.22)

and so `T(n) &lt;= T(n/5) + T(7n/10) + O(n)` fails.

By the way in the Wikipedia example, I get result of recursion as 36. However, the true median is 47.

So, I think in some cases this recursion may not return true median of medians. I want to understand where is my mistake.     


 

All Median of-Medians Solutions on Gang of Coders

Total of 1 Median of-Medians Solutions

Understanding "median of medians" algorithm