Unplugged algorithms: sorting networks

After	W1	W2	W3	W4	W5	W6
Start	12	46	25	33	51	18
Step 1 — (1,6) (2,4) (3,5)	12	33	25	46	51	18
Step 2 — (2,3) (4,5)	12	25	33	46	51	18
Step 3 — (1,4) (3,6)	12	25	18	46	51	33
Step 4 — (1,2) (3,4) (5,6)	12	25	18	46	33	51
Step 5 — (2,3) (4,5)	12	18	25	33	46	51

Comparison by comparison: Step 1 — (1,6) 12 against 18, 12 is smaller and already above, nobody moves; (2,4) 46 against 33, swap; (3,5) 25 against 51, stay. Step 2 — (2,3) 33 against 25, swap; (4,5) 46 against 51, stay. Step 3 — (1,4) 12 against 46, stay; (3,6) 33 against 18, swap. Step 4 — (1,2) 12 against 25, stay; (3,4) 18 against 46, stay; (5,6) 51 against 33, swap. Step 5 — (2,3) 25 against 18, swap; (4,5) 46 against 33, swap.

Step 3 was the strange one. After step 2 the top four wires held 12, 25, 33, 46 and they were already in order, so we expected the network to leave them alone. Instead (3,6) pulled 18 up from the bottom into wire 3 and pushed 33 down, which made the top look worse for a moment. It only came right in step 5. So a step of an algorithm does not have to improve things to be useful — it has to move the right numbers into reach of the comparators that come next.

Test 1 — worst case, 51, 46, 33, 25, 18, 12. Out comes 12, 18, 25, 33, 46, 51. It was actually the fastest run of the three: step 1 swapped all three pairs (51/12, 46/25, 33/18) giving 12, 25, 18, 46, 33, 51, step 2 swapped both pairs giving 12, 18, 25, 33, 46, 51, and steps 3, 4 and 5 then had nothing left to do. The worst possible input for a person is not the worst input for this network.

Test 2 — already sorted, 12, 18, 25, 33, 46, 51. Out comes 12, 18, 25, 33, 46, 51 and there are zero swaps. All twelve comparisons still happen — the network cannot skip them, because no comparator knows what any other comparator found. A network always does the same amount of work whatever goes in.

Test 3 — repeats, 3, 3, 7, 1, 7, 1. Out comes 1, 1, 3, 3, 7, 7. The rule still works: when the two cards are equal, "the smaller goes up" means neither is smaller, so nobody moves. Either choice would give the same answer, so equal values are safe.

Our comparators, in order: (1,2)   (2,3)   (1,2).

Test with 3 on wire 1, 1 on wire 2, 2 on wire 3. (1,2): 3 against 1, swap → 1, 3, 2. (2,3): 3 against 2, swap → 1, 2, 3. (1,2): 1 against 2, stay → 1, 2, 3. Sorted.

We then tried all six possible orders of 1, 2 and 3 and every one came out 1, 2, 3.

1. 12 comparators: 3 + 2 + 2 + 3 + 2.

2. 5 steps, because the comparators inside one step never share a wire, so all of them can happen at the same time.

3. 6 × 5 ÷ 2 = 15 comparisons to compare every pair. The network does only 12, so it already does three comparisons fewer. The bigger saving is the time: 12 comparisons but only 5 steps, because up to three happen at once. Comparing every pair one at a time would take 15 steps — three times as long.

4. Three comparators. Two is not enough: with (1,2) then (2,3), put in 2, 3, 1. The first comparator compares 2 and 3 and leaves them alone; the second compares 3 and 1 and swaps them, giving 2, 1, 3 — wrong. Whatever two comparators you choose, some pair never meets after the other numbers have moved, so an input exists that defeats it.

After	W1	W2	W3	W4	W5	W6
Start	1085	893	886	905	1001	915
Step 1 — (1,6) (2,4) (3,5)	915	893	886	905	1001	1085
Step 2 — (2,3) (4,5)	915	886	893	905	1001	1085
Step 3 — (1,4) (3,6)	905	886	893	915	1001	1085
Step 4 — (1,2) (3,4) (5,6)	886	905	893	915	1001	1085
Step 5 — (2,3) (4,5)	886	893	905	915	1001	1085

Wire 1 ends up holding 886 m — Pen y Fan, the lowest of the six. Wire 6 holds 1085 m, Yr Wyddfa. Note that Yr Wyddfa reached wire 6 in step 1 and never moved again: the network puts the largest value in place first.