# 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.&#x20;
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.
