> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/math/sort5.md).

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