Median of Medians Algorithm for finding the median of an array of numbers

I take issue with this: "Line up elements in groups of five (this number 5 is not important, it could be e.g. 7 without changing the algorithm much)."<p>The correct statement is that you can replace 5 with any <i>larger</i> number and the algorithm still works, but 5 is the least number you can pick here. That's the most interesting part of the algorithm to me - that "5" is connected to median-finding in the same way that "2" is connected to divide in conquer searching in a sorted array. But 2 is more obviously interesting than 5 (you can say "dividing something in 2 makes it smaller", but there aren't very many similar things you can say about 5).

Here's a good public domain implementation of some fast median algorithms, in C.<p><a href="http://ndevilla.free.fr/median/median/index.html" rel="nofollow">http://ndevilla.free.fr/median/median/index.html</a><p>I've used these codes on some very large datasets, and they work very well.

I feel that radix sort would be a better choice, and maybe faster as well. MSB in-place radix sort can sort an arbitrary range, which can be used to find the median very quickly. You simply count the elements for each buckets, and then continue with the bucket containing the median value.<p>Of course, this requires 0 comparisons (but you might want to to a insertion sort for the final round), and a maximum of 4 rounds for 32 bits numbers using 8 bits buckets.

The title is wrong - this algorithm (as the article explains) finds a value near the median, not the actual median. This value is useful as a qucksort pivot but is not the median. Edit: oops, I'm wrong. I missed the recursion step that uses this to get the median.<p>The median of medians is not necessarily the median. E.g. take 1 2 5, 3 4 6, 7 8 9: medians are 2, 4, 8. Median of medians is 4 but overall median is 5.

How do you get the median of 5 items in 6 comparisons? I can see how to do it in 9, but not 6.<p>Edit:<p>Found an answer:<p><a href="http://stackoverflow.com/questions/4761405/compute-median-of-up-to-5-in-scala" rel="nofollow">http://stackoverflow.com/questions/4761405/compute-median-of...</a>

Love that algorithm. Wikipedia has a good visualization for those interested: <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Selection_algorithm#Linear_gene...</a>

Is there something about the page that I'm missing? Is it just about median of median pivot selection for the selection problem? If so, isn't this fairly common knowledge? I know my entry-level algorithms class covered it in some depth.