Sorting five items with the fewest comparisons
What is the smallest number such that some comparison-based procedure always sorts 5 distinct items using at most comparisons (worst case over all inputs)?
Show hints (3)+
- Each comparison has two outcomes; how many orderings must be told apart?
- Start with two pairwise comparisons and compare their winners, building a chain with on the side.
- When you insert the last item, use what you already know about it to search among only 3 items.
Answer
Reveal answer →Final answer
7
Create a free account to see the full worked solution and track your progress.
Interview format: Trading Aptitude Tests, Prop Trading