Last week in my Advanced Algorithms class, we discussed how to create a deterministic algorithm to find the kth smallest element in a list of size n. An algorithm that solves this problem is called a Selection algorithm.
The first step in the deterministic algorithm is to divide the original list into ceil(n/5) lists (each of size 5). The next step is to find the median of each 5 element list. Because 5 is a constant (with respect to n), it is acceptable to first sort each 5 element list and then extract the media (without adversely effecting the runtime).
Now, the Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition) by Kunth says that sorting 5 elements can be done in 7 comparisons. That is great, but we actually do not need to sort these 5 elements. We only need to find the median. Our class found some lecture notes from another class where the professor mentioned in passing that the median of 5 elements can be found with only 6 comparisons, but he never expained how to do this.
I was not aware of nor have I found any results of the form: Finding the median of n elements requires c comparisons. However, I was able to discover how to find the median of 5 elements by using only 6 comparisons. It was not in a paper or even some professional-looking site. It was in a forum which I am only able to view using Google's cached copy. About halfway down the page is the following figure:
This is a remarkably thorough answer. Other than two meaningless typos at the bottom (where he should have said "(C>D gives full ordering)" on the left side and should have said "(C>E gives a full ordering)" on the right side), this solution clearly shows that 6 comparisons is sufficient.
It seems unlikely that there could be a way to find the median of 5 elements with only 5 comparisons, but I have not seen any proof of such a fact. If you know a proof that 6 is indeed the minimum number of comparisons necessary to find the median of 5 elements or if you know any results for lists of larger sizes, please leave a comment.