SORT5

Suppose you are given 25 distinct integers and a function, SORT5, that can sort five integers at a time. Compute the largest, second-largest, and third-largest integers among those 25 integers using SORT5 function and minimize the number of calls to SORT5.

Reference: EPI python, page 200

Solution:

Idea: (6 sorting in total)

1. Split the 25 integers into 5 groups randomly, each group has 5 integers.

2. Sort 5 groups individually.

3. let $m_1, m_2, m_3, m_4, m_5$ be the largest integer in each group, sort these 5 integers. Suppose we have $m_1 > m_2 > m_3 > m_4 > m_5$ . Then $m_1$ is the largest integer.

4. To get the second largest integer, $m_2$ is a candidate, and second largest value in the 1st group $a_1$ is another candidate.

5. To get the third largest integer, $m_2, m_3$ are candidates, second largest value in the 1st group $a_1$ , third largest value in the 1st group $a_2$, and second largest integer in the second group $b_1$ are also candidates. Thus we need to sort $a_1, a_2, m_2, b_1, m_3$ to get the second largest and third largest.