What is the least number of comparisons we need to find the median of 6 distinct numbers?
I am able to find the answer to the median of 5 distinct numbers to be 6 comparisons, and it makes sense, however in the case of 6 numbers I can't find an answer.
The best I was able to do it in by hand was 9 comparisons. Can that be minimized further?
Edit: Median in this case, we are assuming to be the lower median.
It takes at least 8 and can be done in exactly 8.
EDIT
As pointed out by hardmath, the lower bound below is actually an upper bound on the lower bound. JeffE's notes which I link at the bottom give a value of $7$, not $8$.
See this cstheory question here (again thanks to hardmath): https://cstheory.stackexchange.com/questions/12257/exact-number-of-comparisons-to-compute-the-median/12287#12287
which does indeed say the value is $8$.
Note: the below is an incomplete proof.
Lower Bound
A lower bound to find all the $k$ smallest elements is given here: Lower bounds for Selection.
Which says we need at least
$$ n - k + \sum_{n+1-k < j \le n} \lceil \log_{2} j \rceil $$
For $n=6, k=3$, this gives $9$.
$$ 6 - 3 + \lceil \log_{2} 5 \rceil + \lceil \log_{2} 6 \rceil = 9$$
Thus to find the smallest, second smallest and the third smallest, we need at least $9$ compares.
Now any algorithm which finds the $3^{rd}$ smallest element (say $z$) will have to find the set $S = \\{x, y \\}$ such that $x < z$ and $y < z$ (otherwise how does it know that $z$ is the third largest?).
An extra compare between $x$ and $y$ will now give us the smallest, second smallest and third smallest numbers.
Thus any algorithm which finds the third smallest must use at least 8 comparisons.
Upper Bound
As I.J. Kennedy notes, there is an algorithm to find the 3rd smallest element of 6 elements in 8 comparisons and can be found in Knuth's Art of Computer Programming Vol 3, Page 212.
According to Knuth, this is a result obtained by A. Hadian and M. Sobel [Univ of Minnesota, Dept of Statistics Report 121 (169)] and they show that the $k^{th}$ largest element can be found in
$$ n - k + (k-1) \lceil \log_{2} (n+2-k) \rceil $$
comparisons. For $n=6$ and $k=4$ we get the upper bound of $8$.
Algorithm
The way they do it (Knuth's book has all this information) is:
First create a knockout tournament on $n-k+2$ items, which takes $n-k+1$ compares.
The largest item (say $L$) of this cannot be a candidate. So of the remaining $k-2$ pick one and follow the path of $L$ up the tree, which gives the the new largest in at most $\lceil \log_{2} n+2-k \rceil$ compares. Remove this new largest, replacing it with one of the remaining and following up the path of this new largest.
Continue till the rest of the $k-2$ are exhausted. Finally replace the largest with $-\infty$ and determine the largest of the remaining $n+1-k$ which will be the $k^{th}$ largest as we have removed the largest $k-1$ so far.
Related: http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf
It looks like the answer is 8.
My Knuth Volume Three (1970s—not as dusty as you think) reports an upper bound of 8, which, paired with Moron's lower bound of 8, ...
The general form of this question is called the Selection Problem. If you google that phrase you will get lots of useful results.
Edit: Knuth doesn't give an explicit algorithm for finding the median of 6 elements in at most 8 steps (at least in the first edition). However, in exercise 12 of section 5.3.3, he does give the explicit method for finding the median of 7 elements using at most 10 comparisons, which may be of some help.
