Sorting Network

What if multiple comparisons happened at the exact same instant?

Year 9 Computer Science — Parallel Sorting

The Setup

6 volunteers. Each holds a number card. Stand in starting positions.

The rule at every comparator:

When two people meet — lower number moves LEFT, higher number moves RIGHT.

All comparators in the same LAYER fire simultaneously.

Layer by Layer

Layer 1: compare (1,2), (3,4), (5,6)  ← all at once
Layer 2: compare (1,3), (2,6)          ← all at once
Layer 3: compare (2,3), (4,5)          ← all at once
Layer 4: compare (1,4), (3,6)          ← all at once
Layer 5: compare (2,4), (3,5)          ← all at once

Follow each layer. After 5 layers — are you sorted?

Walk the Network!

Teacher calls each layer.

All pairs in that layer move simultaneously.

After 5 layers — check your order!

Count the Steps

Bubble Sort (6 items)

Comparisons: up to 15

Sequential passes: 5

Time steps: 5 (sequential)

Sorting Network

Comparators: 12

Layers: 5

Time steps: 5 (parallel!)

Same time steps — but the network does multiple comparisons per step!

The Parallel Advantage

The sorting network doesn't do fewer comparisons overall — it does them in parallel.

Analogy: 5 people washing 5 plates simultaneously vs 1 person washing them one by one.

Same total work. Much less time.

Real World: Hardware Sorting

CPUs — multiple cores execute simultaneously
GPUs — thousands of cores, sorting massive datasets in parallel
Custom chips — sorting networks wired directly in silicon; nanosecond speed
Network switches — route packets using fixed sorting logic

Extension: Design Your Own

Design a sorting network for just 4 inputs.

How many comparators do you need minimum?
How many layers?
Test it with input [4,3,2,1] — does it produce [1,2,3,4]?

Key Takeaway

Sorting networks run comparisons in parallel — multiple at the exact same instant.

Fewer time steps — not fewer comparisons.

This is how hardware sorts at nanosecond speeds.