TAOCP Vol 3: Sorting and Searching · Week 84
TAOCP 5.3.4 Networks for Sorting: reading guide
Sorting networks: fixed sequences of compare-exchange operations that do not depend on the data. Knuth covers the zero-one principle, Batcher's networks, optimal small networks, and related merging and selection networks.
Time About 9 hours this week
Why it matters
Sorting networks are used in GPUs, SIMD code and hardware because they are branch-free and parallel. The zero-one principle is a great proof trick.
Before you start
- 5.3.1 Minimum-Comparison Sorting
How to approach it
Draw a few networks for 4 and 5 elements. Write a program that verifies a network by testing all 0-1 inputs. Implement Batcher's bitonic or odd-even merge network.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Verifying a network on random inputs only. Use the zero-one principle to test exhaustively.