I have found so many articles regarding median of median but no where I find any satisfactory answer. My professor taught me regarding the topic in which he mentioned that we group the given array in size of 5 and find the medians of these groups . store them in another array and recursively do the previous step until we obtain a single group . The median of this group will be the median of the array and so it could be done in order of n time.
But I didn’t find the same in other text books and lectures .What is mentioned there is that the result divide the array into 30:70 ratio in worst case.
A nice paper explaining all you want to know and more about median of median and real life improvements, as median of ninthers, was written by Andrei Alexandrescu