← CS Unplugged

CS Unplugged activity

Beat the Clock: A Sorting Network

About 25 minutesSoloPencil

Computers put lists in order all the time: high scores, search results, contacts by name. One way to sort faster is to compare several pairs of numbers at the same time instead of one pair at a time. The diagram below is a sorting network: a fixed set of comparisons wired together so that six numbers always come out in order, no matter what order they started in.

How to trace it

  1. Six starting numbers sit at the top of six lines, called wires.
  2. Follow two wires down to the first short line connecting them. That is a comparator.
  3. Compare the two numbers there. Write the smaller one in the left box, the larger one in the right box.
  4. Follow each wire down to its next comparator and repeat.
  5. At the bottom, read the six boxes top to bottom. They should be sorted.

Worked example: two wires carrying 9 and 4 meet at one comparator. 4 is smaller, so it goes in the left box. 9 is larger, so it goes in the right box.

9 4 4 9

This network compares six numbers 15 times in total, but never more than 3 comparisons wait on each other, so it only takes 6 rounds from top to bottom.

Check yourself: the last row of boxes in Round 1 and Round 2 should read in increasing order top to bottom, and Round 3’s last row should read in alphabetical order. If a row does not, retrace the comparator just above the box that looks wrong.

Why is this fast?

Look back at your diagram. Count every circle in the round that has the most comparators.

How many comparisons happen at the exact same time in that round?

Now count every circle you passed through, top to bottom, tracing just one of your number rounds. A computer comparing only one pair at a time would need that many separate steps. This network gets the same six numbers sorted in just 6 rounds, because several of those comparisons happen together instead of waiting in line.

Learn more: this shape of network is called a sorting network, and real computer chips use the same idea to sort many numbers at once.

Traced boxes

Adapted from CS Unplugged, 2015, by Tim Bell, Ian H. Witten and Mike Fellows; adapted for classroom use by Robyn Adams and Jane McKenzie (csunplugged.org). Licensed under CC BY-NC-SA 3.0.