optimal sorting

Question

I got a solution to the following question, but am unable to provide a proof.

Given 25 distinct integers, one can sort them 5 at a time. What is the least number of sorting to obtain the smallest 3 numbers?

Answer 1

There is a solution with 7 sorts. If we can show that 6 sorts do not suffice to find the smallest 3 numbers, we are done.

When looking for the smallest number one can eliminate 4 numbers with each sort (of 5 numbers). So we need 6 sorts to eliminate 24 numbers to eventually find the smallest number out of 25. Now we will show that one cannot avoid having two candidates for the second smallest number after 6 sorts.

• candidate 1: The second smallest of the 6th sort is a candidate for the second smallest number in total. (For some strategies you can be lucky and be sure that this is the second smallest number; e.g. if you always take the smallest number of a sort into the next sort and then it happens that the smallest number of the 5th sort is second in the 6th sort. But one cannot force this.)
• (potential) candidate 2: As mentioned under "candidate 1" such a candidate 2 for the second smallest number need not exist. But for each strategy an order of how the numbers go into the sorts can be constructed, s.t. such a candidate 2 exists. Since a strategy must work in all cases, only one such construction of number ordering suffices to reject it. In brief the possibility of a second candidate for the second smallest number can be argued as follows: Among the numbers of the 6th sort there will be the smallest number of the 5th sort. Now if this number turns out smallest in the 6th sort (note that any number in the 6th sort could be the smallest one because in the first 5 sorts only 20 numbers could be eliminated from being the smallest one), the second smallest number of the 5th sort is also a candidate for the overall second smallest number.

So we need at least a 7th sort to find the second smallest number (under any order of how the numbers are put into the sorts for a given strategy) and hence also to find the smallest 3 numbers.

Appendix: Let us for example show such problematic number orderings for two specific strategies. The order of how the numbers go into the sorts must be such that the smallest number of the 5th sort is the overall smallest number (and thus the second smallest number of the 5th sort will be the "candidate 2" for the overall second smallest number). Without loss of generality we can assume that the numbers to sort are 1,2,...25.

Strategy 1: The smallest number of each sort goes into the next sort.

When the numbers are in the following, almost reverse, order 25,24,...8,7,2,1,6,5,4,3 and taken one after the other as needed we get the following sorts:

1. 25,24,23,22,21 -> 21,22,23,24,25
1. 21,20,19,18,17 -> 17,18,19,20,21
1. 17,16,15,14,13 -> 13,14,15,16,17
1. 13,12,11,10, 9 ->  9,10,11,12,13
1.  9, 8, 7, 2, 1 ->  1, 2, 7, 8, 9
1.  1, 6, 5, 4, 3 ->  1, 3, 4, 5, 6

From the sorts we only now 1 < 2 and 1 < 3. So both 2 and 3 could be the second smallest number.

Strategy 2 (the one solving the original question): group the numbers by 5 and send these groups into the first 5 sorts. Then take the smallest numbers of the first 5 sorts and put them into the 6th sort.

When the numbers are in the following almost strict ascending order 6,7,...25,1,2,...5 and taken one after the other as needed we get the following sorts:

1.  6, 7, 8, 9,10 ->  6, 7, 8, 9,10
2. 11,12,13,14,15 -> 11,12,13,14,15
3. 16,17,18,19,20 -> 16,17,18,19,20
4. 21,22,23,24,25 -> 21,22,23,24,25
5.  1, 2, 3, 4, 5 ->  1, 2, 3, 4, 5
6.  1, 6,11,16,21 ->  1, 6,11,16,21

After the 6th sort we only know 1 < 2 and 1 < 6, so both 2 and 6 could be the second smallest number.

Like done for these 2 strategies it is possible (by the above proof) to generate an order of how the numbers go into the sorts such that after the 6th sort both the second smallest number of the 5th sort and the second smallest number of the 6th sort are candidates for the overall second smallest number.