Worksheet: Unplugged Algorithms: Sorting Networks

Cover teacher — you need no subject knowledge and no computers

Print: this sheet one per pupil, and the stimulus sheet "The six-wire sorting network" one per pair. If you have floor space and chalk or masking tape, copy the shape onto the ground and cut the six number cards out of the stimulus sheet; if not, everything works at the desk with a pencil.

Run: 5 min read the three rules · 10 min walk or finger-trace the network once with the number cards · 15 min complete the trace table on this sheet · 10 min the three "does it always work?" tests · 10 min design a three-wire network and answer the counting questions.

Collect: this sheet. The correct trace table, the three test answers and the three-wire design are all on the worked example sheet, so you can mark it in a couple of minutes.

What you are doing

A sorting network is an algorithm you can walk through. Six numbers go in on the left, and if everybody obeys the same three rules, the numbers always come out in order on the right — without anybody being in charge and without anybody seeing more than two numbers at a time. Your job is to trace the network, test whether it really always works, and then build a smaller one of your own.

Step by step

Trace table — Card set B

Start with 12, 46, 25, 33, 51, 18 on wires 1 to 6. After each step, write what is on each wire. Nothing moves except at a coloured bar.

After

Wire 1

Wire 2

Wire 3

Wire 4

Wire 5

Wire 6

Start

Step 1 — (1,6) (2,4) (3,5)

Step 2 — (2,3) (4,5)

Step 3 — (1,4) (3,6)

Step 4 — (1,2) (3,4) (5,6)

Step 5 — (2,3) (4,5)

Does it always work? Three tests

Test	What came out, and what that tells you
Test 1 — worst case. Put the numbers in backwards: 51, 46, 33, 25, 18, 12.
Test 2 — already sorted. Put them in as 12, 18, 25, 33, 46, 51. How many swaps happen?
Test 3 — repeats. Use 3, 3, 7, 1, 7, 1. Does the rule "the smaller number goes up" still say what to do when both cards are the same?

Test

What came out, and what that tells you

Test 1 — worst case. Put the numbers in backwards: 51, 46, 33, 25, 18, 12.

Test 2 — already sorted. Put them in as 12, 18, 25, 33, 46, 51. How many swaps happen?

Test 3 — repeats. Use 3, 3, 7, 1, 7, 1. Does the rule "the smaller number goes up" still say what to do when both cards are the same?

Design your own three-wire network

Three wires, three numbers. Draw the comparators you need on the grid, then test it with 3 on wire 1, 1 on wire 2 and 2 on wire 3. Write the comparators as pairs underneath, in order.

Counting questions

Question	Your answer
1. How many comparators are there altogether in the six-wire network?
2. How many steps does it take, if every comparator in a step happens at the same time?
3. Sorting six cards by comparing every pair would take 6 × 5 ÷ 2 comparisons. How many is that, and how does it compare with your answer to question 1?
4. What is the smallest number of comparators a three-wire network needs? How do you know two is not enough?

Question

Your answer

1. How many comparators are there altogether in the six-wire network?

2. How many steps does it take, if every comparator in a step happens at the same time?

3. Sorting six cards by comparing every pair would take 6 × 5 ÷ 2 comparisons. How many is that, and how does it compare with your answer to question 1?

4. What is the smallest number of comparators a three-wire network needs? How do you know two is not enough?

Success criteria

I followed the algorithm exactly as written instead of just sorting the numbers in my head.
My trace table records the state of all six wires after every step, so someone else could check my work.
I tested the algorithm with awkward inputs — reversed, already sorted, and with repeated values.
I designed a smaller network of my own and tested it rather than assuming it worked.
I can explain why doing several comparisons at the same time makes the whole job finish sooner, even though it does not do fewer comparisons.

If you finish early

Trace Card set A, the six Welsh mountain heights, through the network: 1085, 893, 886, 905, 1001, 915 on wires 1 to 6. Which mountain ends up on wire 1?

Build a four-wire network. Five comparators are enough — find an arrangement that works and prove it by testing all the orderings of 1, 2, 3, 4 that you can manage.

Turn one comparator round so the larger number goes up. Find an input that now comes out in the wrong order, and write it down as proof that the network is broken.