Knuth · Weeks 90 to 117

TAOCP Volume 3: Sorting and Searching

The most directly practical volume. Chapter 5 covers sorting: the combinatorics of permutations, every classic internal sort with exact analysis, lower bounds, sorting networks and external sorting. Chapter 6 covers searching: binary search, balanced trees, B-trees, tries, hashing and secondary keys. You will finish it able to read any database or standard library internals. Jonathan Blow put it this way in a clip that helped inspire this path: "If you actually go through [Volume 3] for real, you will know way more data structures than anyone with a CS degree." For real means the exercises too.

28weeks

33reading guides

964exercises

~217hours

Every section, week by week

Section	Week	Exercises	Picked	Time
5.1.1 Inversions	90	29 (10 to M43)	8	7 h
5.1.2 Permutations of a Multiset	91	24 (M05 to M35)	7	7 h
5.1.3 Runs	92	29 (05 to HM42)	8	6 h
5.1.4 Tableaux and Involutions	93	44 (M08 to HM43)	8	9 h
5.2.1 Sorting by Insertion	94	44 (10 to HM43)	8	9 h
5.2.2 Sorting by Exchanging	95	56 (10 to M48)	8	10 h
5.2.3 Sorting by Selection	96	38 (10 to M41)	8	8 h
5.2.4 Sorting by Merging	97	23 (16 to 47)	7	8 h
5.2.5 Sorting by Distribution	98	18 (13 to 40)	7	6 h
5.3.1 Minimum-Comparison Sorting	99	36 (10 to M50)	8	8 h
5.3.2 Minimum-Comparison Merging	100	25 (12 to M47)	7	5 h
5.3.3 Minimum-Comparison Selection	100	27 (10 to M49)	8	5 h
5.3.4 Networks for Sorting	101	68 (M16 to 50)	8	9 h
5.4.1 Multiway Merging and Replacement Selection	102	30 (00 to M46)	8	8 h
5.4.2 The Polyphase Merge	103	31 (11 to M47)	8	5 h
5.4.3 The Cascade Merge	103	13 (10 to M40)	6	3 h
5.4.4 Reading Tape Backwards	104	26 (07 to M46)	8	3 h
5.4.5 The Oscillating Sort	104	5 (21 to 29)	4	3 h
5.4.6 Practical Considerations for Tape Merging	105	16 (13 to 41)	7	6 h
5.4.7 External Radix Sorting	106	7 (15 to M35)	5	3 h
5.4.8 Two-Tape Sorting	106	10 (20 to M40)	6	3 h
5.4.9 Disks and Drums	107	31 (M15 to 49)	8	7 h
5.5 Summary, History, and Bibliography	107	5 (05 to 46)	3	3 h
6.1 Sequential Searching	108	22 (15 to M30)	8	6 h
6.2.1 Searching an Ordered Table	109	30 (15 to M42)	8	7 h
6.2.2 Binary Tree Searching	110	49 (15 to M47)	8	8 h
6.2.3 Balanced Trees	111	33 (01 to M47)	8	9 h
6.2.4 Multiway Trees	112	10 (10 to HM37)	7	8 h
6.3 Digital Searching	113	45 (00 to M43)	8	8 h
6.4 Hashing (part 1)	114	78 (10 to M49)	8	8 h
6.4 Hashing (part 2)	115	78 (10 to M49)	8	9 h
6.5 Retrieval on Secondary Keys	116	20 (19 to M47)	7	7 h
Vol 3 review	117	964 (00 to M50)	8	6 h

Each section links to its reading guide: what it covers, how to approach it, exercises picked from the book with their ratings, common traps and links. Picked is how many exercises the guide recommends; time is its budget for the week.

What you will be able to do

Implement and analyze quicksort, heapsort, merge sort, radix sort and Shellsort.
Explain why comparison sorting needs about n lg n comparisons.
Build AVL trees, B-trees, tries and hash tables, and predict their performance.
Design an external sort for data that does not fit in memory.

Before you start

Vols 1 and 2, especially 1.2 math and 2.3 trees.
Your clox hash table (chapter 20) as a reference point for 6.4.

Getting the book

The current edition is the second edition (1998), ISBN 0-201-89685-0.

Vol 3, 2nd edition is about $64 new from InformIT. The 1st edition (1973) is fine and often very cheap used. Borrow before you buy: many public and university libraries give you free access to O'Reilly Learning, which carries TAOCP; Libby/OverDrive and interlibrary loan (search WorldCat) work too. Older used editions are fine for Vols 1 to 3; section numbers barely changed. If you buy the eBook, get the PDF from InformIT. Knuth himself warns that the Kindle and ePUB versions mangle the math.

What you need has every option with prices, and which edition do I need covers the differences.

Tips

The tape-sorting sections (5.4.2 to 5.4.8) are mostly historical; skim them and spend the time on 5.4.1 and 5.4.9.
Build one shared benchmark harness for all your sorts.

Questions

How long does TAOCP Volume 3 take?

On the cracked.guide path it takes 28 weeks (weeks 90 to 117), about 6 months, and the reading guides budget about 217 hours in all.

How many exercises are in TAOCP Volume 3?

964 in the sections the path covers, rated 00 to M50, and 217 of them carry Knuth's triangle for recommended. Each reading guide picks the ones worth your time.

Which edition of Volume 3 do I need?

The current one is the second edition (1998). Older used editions work for most of it; section numbers barely changed. Buy the PDF, not Kindle, if you want an eBook.