The smallest sorting network on four wires
A sorting network is a fixed sequence of comparators; comparator with swaps the values on wires and if they are out of order. The sequence is the same for every input (no branching). What is the minimum number of comparators in a network that sorts every input of 4 values?
Show hints (3)+
- Sort the two pairs, then route the min and the max to the ends.
- The 0-1 principle: it is enough to check inputs made of 0s and 1s.
- How many comparators does placing both the min and the max require, and what is left unsorted?
Answer
Reveal answer →Final answer
5
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading