Find 3rd largest number out of 7 under at most 11 comparisons I know similar problem like "sort 5 numbers in 7 comparisons". I know no general algorithms exist. Do I just enlist all possible game trees?
 A: Let $V_t(n)$ be the minimum number (in the worst case) of comparisons needed to find the $t$th largest of $n$ distinct values (selection algorithms).
Knuth (AOCP 5.3.3) describes a good method to find the required entry, the constructive basis for an upper bound (11), Hadian and Sobel's theorem:
$$ V_t(n) \leq n - t + (t-1) \lceil \lg(n+2-t) \rceil $$
In the immediate case this gives $V_3(7) \leq 4+2\lceil \lg 6 \rceil = 10 $, which is within the limit prescribed in this Question's title.
The general method is to set up a binary tree "knockout tournament" on $n-t+2$ of the entries, keeping $t-2$ of them in reserve.  This requires $n-t+1$ comparisons, and produces a "winner" which exceeds (at least) $n-t+1$ of all the other entries.  Since the $t$th largest entry exceeds only $n-t$ entries, it cannot be that winner.  Replace the winner at the base (not the top) of the binary tree/tournament with one of the reserve entries, and recompare.  Since this affects only one path (from base to top) in the tournament, this requires at most $\lceil \lg(n+2-t) \rceil$ added comparisons.  Repeating this for each reserve entry, $t-2$ times in all, we are down to a set of $n-t+2$ entries whose current winner is also not the entry we want.  Finally, replace that last winner with an entry that a priori loses every comparison, and again recompare (affecting only one path in the tree), which takes at most $\lceil \lg(n+2-t) \rceil - 1$ comparisions (taking advantage of the sure loser not to actually do a comparison).  The $t$th largest entry comes out on top, in total using at most the number of comparisons given in the right hand side of the above inequality.
For the specific case $n=7$ and $t=3$, our initial knockout tournament would involve six of the entries, holding just one entry R in reserve. This uses five comparisons * to determine an initial winner X, which could have come from anywhere in the tree's base:
                               X
                               *
                              / \
                             /   \
                            *     \
                           / \     \
                          /   \     \
                         *     *     *
                        / \   / \   / \        |
                       ?   X ?   ? ?   ?       R

The depth of the binary tree is three, so recomparing after replacing the initial winner X with the reserve entry R results in at most three new comparisons # to find our second winner Y:
                               Y
                               #
                              / \
                             /   \
                            #     \
                           / \     \
                          /   \     \
                         #     *     *
                        / \   / \   / \
                       ?   R ?   ? ?   ? 

Finally, after putting a sure loser in place of second winner Y, recomparing produces the 3rd largest entry Z.  This takes at most two new comparisons because the first comparison that Y took to the top of the tree is "skipped" by the sure loser.  In total:
$$ V_3(7) \leq 5 + 3 + 2 = 10 $$
This turns out to be the sharp minimum number of comparisons possible in the worst case, as $V_3(7) = V_4(7) = V_5(7) = 10$ (see Knuth's AOCP, Vol. 3 Sorting and Searching, in Table I of Sec. 5.3.3, or the expanded table here by Ken Okansen).



*

*Hadian, Abdollah and Milton Sobel  "Selecting the t-th largest using
binary errorless comparisons," Technical Report 121, Dept. of
Statistics, Univ. of Minnesota, May 1969 (15 pp.)

