TAOCP 5.2.4 Sorting by Merging: reading guide

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.