# Minimum number of comparisons sufficient to rank any set of $n$ objects?

Say you're given a set of objects, and you don't know the value of any of the objects, but, given a pair of two objects you are always told which one is bigger.

For a set $\{x_1, x_2, \cdots, x_n\}$, what is the minimum number of comparisons that will suffice to put all of its elements in ascending order of size: i.e. of the form $$\{y_1, y_2, \cdots, y_n\}$$ where $y_i\lt y_{i+1}$ for all $i$?

Obviously this is easy to determine for small $n$ (by trial and error), but as $n$ increases, I'm not sure which comparisons are redundant.

• This is $n\log(n)$ asymptotically - well studied. See en.wikipedia.org/wiki/Sorting_algorithm. – Ethan Bolker Feb 27 '16 at 1:48
• There are a total of $n!$ permutations, hence you need at least $\log_2 n!\sim n\log_2 n$ comparisons. – A.S. Feb 27 '16 at 2:14
• @EthanBolker How should I turn that into an integer? Obviously $n \log (n)$ is not always a whole number. – beep-boop Feb 27 '16 at 4:00
• @RobArthan What I mean is: what's the max number of comparisons needed to be able to list all elements of the set in order of size. – beep-boop Feb 27 '16 at 4:03
• As of Aug 2011, the exact value of minimum number of comparision is not known for $n = 16$, see OEIS A036604. – achille hui Feb 27 '16 at 4:29