Week 80 of 125
TAOCP 5.2.4 Sorting by Merging
Sign up or sign in to tick these off and give this week a due date.
-
Merging two sorted lists, two-way merge sort on arrays (natural and straight versions), and list merge sort that works on linked records without moving data.
Time About 8 hours this week
Why it matters
Merge sort is stable and the basis for Timsort (Python, Java objects) and for external sorting. List merge sort is the right way to sort linked lists.
Before you start
- 5.2.1 to 5.2.3
How to approach it
Implement top-down and bottom-up merge sort on arrays and list merge sort on a linked list. Check stability with records that have equal keys.
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
- Integer overflow computing the midpoint as (lo + hi) / 2 on huge arrays.
- Breaking stability by taking from the right run on ties.