Week 81 of 125
TAOCP 5.2.5 Sorting by Distribution
Sign up or sign in to tick these off and give this week a due date.
-
Radix sorting: distributing records into piles by digit, least significant digit first, using linked lists to avoid moving data, with analysis of when it beats comparison sorts.
Time About 6 hours this week
Why it matters
Radix sort is how you sort integers, strings and fixed-size keys fast. It shows up in GPU sorting and database engines.
Before you start
- 5.2.4 Sorting by Merging
How to approach it
Implement LSD radix sort on 32-bit integers with byte-sized digits and counting sort per pass. Benchmark it against your quicksort.
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
- Non-stable distribution passes break LSD radix sort.