<s>[INST] Application of Mergesort We have $8$ players and we want to sort them in $24$ hours. 
There is one stadium. Each game lasts one hour. 
In how many hours can we sort them?? 
I thought that we could it as followed:
$$\boxed{P1} \ \boxed{P2} \ \boxed{P3} \ \boxed{P4} \ \boxed{P5} \ \boxed{P6} \ \boxed{P7} \ \boxed{P8} \\ \ \ \ \ \boxed{P1} \ \ \ \ \ \ \ \ \  \boxed{P3} \ \ \  \ \ \ \ \ \boxed{P5} \ \ \  \ \ \ \ \ \ \ \ \boxed{P7} \\ \ \  \boxed{P1} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \boxed{P5} \\ \ \ \  \boxed{P1}$$
So, the best player is $P1$. 
These games took place in $7$ hours.
We know that $P5$ is the best player among the players $P5$, $P6$, $P7$ and $P8$.
$$\boxed{P2} \ \boxed{P3} \ \boxed{P4} \  \boxed{P5}\\ \boxed{P2} \ \ \ \ \ \ \boxed{P5} \\ \ \ \boxed{P2}$$
So, the second best player is $P2$.
These games took place in $3$ hours. 
$$\boxed{P3} \ \boxed{P4} \  \boxed{P5}\\ \ \ \ \ \ \boxed{P3}\ \ \ \   \boxed{P5} \\ \ \ \ \ \ \  \boxed{P3}$$
So, the third best player is $P3$.
These games took place in $2$ hours.
$$\boxed{P4} \  \boxed{P5}\\ \ \ \boxed{P4}$$
So, the $4^{th}$ best player is $P4$ and the $5^{th}$ best player is $P5$. 
This game took place in $1$ hour.
$$\boxed{P6} \ \boxed{P7} \  \boxed{P8}\\ \ \ \ \ \ \boxed{P6}\ \ \ \   \boxed{P8} \\ \ \ \ \ \ \ \boxed{P6}$$
So, the $6^{th}$ best player is $P6$.
These games took place in $2$ hours. 
$$\boxed{P7} \  \boxed{P8}\\ \ \ \ \ \boxed{P7}$$
So, the $7^{th}$ best player is $P7$ and $8^{th}$ best player is $P8$.
This game took place in $1$ hour. 
Therefore, we sorted the players $P1 \geq P2 \geq P3 \geq P4 \geq P5 \geq P6 \geq P7 \geq P8$ in $7+3+2+1+2+1=16$ hours. 
Is it correct?? 
Is it maybe an application of Mergesort??
EDIT: 
In the case when we have more than one stadium is it as followed??
$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \boxed{P1} \ : \ \boxed{P2} \ \ \ \ \ \ \ \ \boxed{P3} \ : \ \boxed{P4} \ \ \ \ \ \ \ \ \boxed{P5} \ : \ \boxed{P6} \ \ \ \ \ \ \ \ \boxed{P7} \ : \ \boxed{P8} \Rightarrow 4 \text{ Stadiums } \\ \boxed{P1} \ > \ \boxed{P2} \ \ \ \ \ \ \ \ \boxed{P3} \ > \ \boxed{P4} \ \ \ \ \ \ \ \ \boxed{P5} \ > \ \boxed{P6} \ \ \ \ \ \ \ \ \boxed{P7} \ > \ \boxed{P8}$$
$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \boxed{P1} \ : \ \boxed{P3} \ \ \ \ \ \ \ \ \boxed{P2} \ : \ \boxed{P4} \ \ \ \ \ \ \ \ \boxed{P5} \ : \ \boxed{P7} \ \ \ \ \ \ \ \ \boxed{P6} \ : \ \boxed{P8} \Rightarrow 4 \text{ Stadiums } \\ \boxed{P1} \ > \ \boxed{P3} \ \ \ \ \ \ \ \ \boxed{P2} \ > \ \boxed{P4} \ \ \ \ \ \ \ \ \boxed{P5} \ > \ \boxed{P7} \ \ \ \ \ \ \ \ \boxed{P6} \ > \ \boxed{P8}$$
Now we know tht $P1 >P2>P4$ and $P1>P3>P4$, that means that we have to know whether $P2>P3$ or $P3>P2$.
Also, we know that $P5>P6>P8$ and $P5>P7>P8$, that means that we have to know whether $P6>P7$ or $P7>P6$.
So, we have the following: 
$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \boxed{P2} \ : \ \boxed{P3} \ \ \ \ \ \ \ \ \boxed{P4} \ : \ \boxed{P5} \ \ \ \ \ \ \ \ \boxed{P6} \ : \ \boxed{P7} \Rightarrow 3 \text{ Stadiums } \\ \boxed{P2} \ > \ \boxed{P3} \ \ \ \ \ \ \ \ \boxed{P4} \ > \ \boxed{P5} \ \ \ \ \ \ \ \ \boxed{P6} \ > \ \boxed{P7}$$
So, we have sorted them $P1>P2>P3>P4>P5>P6>P7>P8$ in $3$ hours.
Is it correct??
 [/INST] I think that the question is: if we wish to sort $n$ items by comparing them two at a time, and the algorithm is completely determined by the results of those comparisons, what is the minimum number of comparisons that we need to make?
For example, if there are $n = 3$ items, there are 6 possible arrangements, and we need to make some comparisons to see which is the "correct" arrangement. In this case, we will need at least 3 comparisons. The first comparison (say, of P1 and P2) will cut us down to three possible "true" arrangements. But there is no second comparison that, regardless of its outcome, will reduce this to one possible comparison. Therefore, we will need a third comparison in the worst case. 
More information about this is written in Wikipedia under Comparison sort. 
The exact number of comparison needed to sort $n$ items in the worst case, assuming an optimal algorithm, is apparently unknown. It is sequence A036604 in the OEIS. That web page does show that 16 is the least number possible for $n = 8$ items, as in the question.  But the lack of any formula on that page suggests that, in general, the problem is quite difficult.  In particular, the merge sort example is not likely to generalize to arbitrary $n$. 
</s>