Skip to content
Get started

The smallest sorting network on four wires

A sorting network is a fixed sequence of comparators; comparator (i,j)(i, j) with i<ji < j swaps the values on wires ii and jj 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)+
  1. Sort the two pairs, then route the min and the max to the ends.
  2. The 0-1 principle: it is enough to check inputs made of 0s and 1s.
  3. How many comparators does placing both the min and the max require, and what is left unsorted?

Answer

Reveal answer →

5

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

Interview format: Prop Trading

Related questions