Sorting Networks

Lesson 9 of 11 · 7 min · Free, no account needed

What you will learn

A comparator takes two numbers and sends the smaller up, the bigger down.
A sorting network is a fixed drawing of comparators that sorts any input.
Comparators on different wires can work at the same moment: that's parallelism. 12 comparisons in just 5 rounds.

A chalk drawing and one rule at each crossing: the smaller goes up. Can a drawing sort?
Put the four numbers on the inputs in any order, then Run.
Six wires. Watch it round by round.
Step fires one round. Count comparisons and rounds.
Try to break it.
Shuffle the inputs with the swap buttons, then Run. Six tries to get an output out of order.
Sorting networks.
A comparator takes two numbers and sends the smaller up and the bigger down.
A sorting network is a fixed arrangement of comparators that sorts every possible input. It never looks at the data to decide what to do next.
Comparators on different wires can work at the same moment: parallelism. Six numbers take 12 comparisons but only 5 rounds.
These comparators are drawn one after another. Which can fire together, first?
Tap them, then Check.
Two comparators can run at the same time only if they share no wire and neither needs a result the other is still producing.
This network lost a comparator.
Run it, see what comes out, then add the missing one.
Build your own network for 3 numbers.
Three comparators. Test all 6 orders, then Check.
After the first two comparators the biggest number has been pushed down to wire 3. The last comparator then sorts the top two.
A million comparisons. How many workers to finish in 1000 ticks?
Each worker does one comparison per tick, all at once.
Your network, on every input.
Run all six orders through the network you built.

Lessons are interactive and need JavaScript. Turn it on to play them.