Application of Mergesort

Question

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??

Answer 1

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$.

Answer 2

The idea of mergesort is to exploit the fact, that merging two pre-sorted lists is "cheap": if the lenght of list1 is $l_1$ and that of list2 is $l_2$ and $L=l_1+l_2$ then you need at most $L-1 $comparisions to make a sorted list. The minimum (in a simple algorithm) is just the length of the shorter list.
This idea can be "iterated": each of the lists may have been built from two shorter lists, say list1 = merge(list11,list12) and list2=merge(list21,list22) and the sum of the comparisions is again the sum of the four partial lists-lenghtes, which is again $L-1$. If you have at the beginning a list of 16 elements, we could generate it by at most 16 comparisions provided its two partial lists each of length 8 are already sorted. Thus if we have 4 lists each of them with length 4, presorted, then we need at most 2*16 comparisions. The same with one more iteration: if we have 8 lists each of 2 elements,presorted, we need 3*16 comparisions to sort the list completely. Now each list of 2 elements can be sorted by 1 comparision so we get, in the worst case 8+3*16=56 comparisions. (If the overall list length is not a perfect power of 2 the highest number of comparisions must be computed more seriously).
In this simple algorithm it can happen, that the same two elements are compared twice in the process. With real matches, one could then omit that match and look at the protocol instead. With 8 players we should have 4 initial matches to have 4 lists with two elements. Then two lists are merged, that needs two times at most 3 comparisions which is 6 comparisions, and the two remaining lists have 4 elements each which needs 7 comparisions at most and thus we can arrive at the result by 4+6+7=17 comparisions at most.
(Please check my computations of the worst and of the best cases! - I'm just typing from the hand without references)
The idea of the multiple stadiums adds then the possibility to let some matches happen at the same time (and should possibly only put your focus to the idea of generating partial lists (two lists = two stadiums) which shall later be merged)

If the length of the list is large, there are improvements possible: one can merge two long presorted lists using binary search for the initial elements-comparision, but that leads too far here.