Skip to content
Get started

Sorting five items with the fewest comparisons

What is the smallest number cc such that some comparison-based procedure always sorts 5 distinct items using at most cc comparisons (worst case over all inputs)?

Show hints (3)+
  1. Each comparison has two outcomes; how many orderings must be told apart?
  2. Start with two pairwise comparisons and compare their winners, building a chain a<b<da < b < d with c<dc < d on the side.
  3. When you insert the last item, use what you already know about it to search among only 3 items.

Answer

Reveal answer →

7

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Prop Trading

Related questions