TAOCP 5.2.1 Sorting by Insertion: reading guide

Straight insertion, binary insertion, Shellsort with diminishing increments, list insertion, and address-calculation sorting, each with careful analysis.

Time About 9 hours this week

Why it matters

Insertion sort is what fast library sorts use for small subarrays. Shellsort is still a practical choice in embedded code with no recursion.

Before you start

5.1.1 Inversions
1.2.10 Analysis of an Algorithm

How to approach it

Implement straight insertion and Shellsort with a few increment sequences. Count comparisons and moves on random data and compare with Knuth's formulas and tables.

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

Shellsort performance depends hugely on the increment sequence. Do not use powers of two.
Using binary insertion and expecting big wins on arrays: moves still cost O(n^2).