# TAOCP Volume 3: Sorting and Searching > Knuth's The Art of Computer Programming, Volume 3 (second edition, 1998, ISBN 0-201-89685-0), as studied on the cracked.guide path in weeks 90 to 117: 33 reading guides, 964 exercises, about 217 hours. 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](https://www.youtube.com/watch?v=TxCB-GBpmIQ) 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. ## Every section, week by week | Section | Week | Exercises | Picked | Hours | | --- | --- | --- | --- | --- | | [5.1.1 Inversions](https://cracked.guide/guide/knuth-w073-0) | 90 | 29 (10 to M43) | 8 | 7 | | [5.1.2 Permutations of a Multiset](https://cracked.guide/guide/knuth-w074-0) | 91 | 24 (M05 to M35) | 7 | 7 | | [5.1.3 Runs](https://cracked.guide/guide/knuth-w075-0) | 92 | 29 (05 to HM42) | 8 | 6 | | [5.1.4 Tableaux and Involutions](https://cracked.guide/guide/knuth-w076-0) | 93 | 44 (M08 to HM43) | 8 | 9 | | [5.2.1 Sorting by Insertion](https://cracked.guide/guide/knuth-w077-0) | 94 | 44 (10 to HM43) | 8 | 9 | | [5.2.2 Sorting by Exchanging](https://cracked.guide/guide/knuth-w078-0) | 95 | 56 (10 to M48) | 8 | 10 | | [5.2.3 Sorting by Selection](https://cracked.guide/guide/knuth-w079-0) | 96 | 38 (10 to M41) | 8 | 8 | | [5.2.4 Sorting by Merging](https://cracked.guide/guide/knuth-w080-0) | 97 | 23 (16 to 47) | 7 | 8 | | [5.2.5 Sorting by Distribution](https://cracked.guide/guide/knuth-w081-0) | 98 | 18 (13 to 40) | 7 | 6 | | [5.3.1 Minimum-Comparison Sorting](https://cracked.guide/guide/knuth-w082-0) | 99 | 36 (10 to M50) | 8 | 8 | | [5.3.2 Minimum-Comparison Merging](https://cracked.guide/guide/knuth-w083-0) | 100 | 25 (12 to M47) | 7 | 5 | | [5.3.3 Minimum-Comparison Selection](https://cracked.guide/guide/knuth-w083-1) | 100 | 27 (10 to M49) | 8 | 5 | | [5.3.4 Networks for Sorting](https://cracked.guide/guide/knuth-w084-0) | 101 | 68 (M16 to 50) | 8 | 9 | | [5.4.1 Multiway Merging and Replacement Selection](https://cracked.guide/guide/knuth-w085-0) | 102 | 30 (00 to M46) | 8 | 8 | | [5.4.2 The Polyphase Merge](https://cracked.guide/guide/knuth-w086-0) | 103 | 31 (11 to M47) | 8 | 5 | | [5.4.3 The Cascade Merge](https://cracked.guide/guide/knuth-w086-1) | 103 | 13 (10 to M40) | 6 | 3 | | [5.4.4 Reading Tape Backwards](https://cracked.guide/guide/knuth-w087-0) | 104 | 26 (07 to M46) | 8 | 3 | | [5.4.5 The Oscillating Sort](https://cracked.guide/guide/knuth-w087-1) | 104 | 5 (21 to 29) | 4 | 3 | | [5.4.6 Practical Considerations for Tape Merging](https://cracked.guide/guide/knuth-w088-0) | 105 | 16 (13 to 41) | 7 | 6 | | [5.4.7 External Radix Sorting](https://cracked.guide/guide/knuth-w088-1) | 106 | 7 (15 to M35) | 5 | 3 | | [5.4.8 Two-Tape Sorting](https://cracked.guide/guide/knuth-w089-0) | 106 | 10 (20 to M40) | 6 | 3 | | [5.4.9 Disks and Drums](https://cracked.guide/guide/knuth-w089-1) | 107 | 31 (M15 to 49) | 8 | 7 | | [5.5 Summary, History, and Bibliography](https://cracked.guide/guide/knuth-w090-0) | 107 | 5 (05 to 46) | 3 | 3 | | [6.1 Sequential Searching](https://cracked.guide/guide/knuth-w091-0) | 108 | 22 (15 to M30) | 8 | 6 | | [6.2.1 Searching an Ordered Table](https://cracked.guide/guide/knuth-w092-0) | 109 | 30 (15 to M42) | 8 | 7 | | [6.2.2 Binary Tree Searching](https://cracked.guide/guide/knuth-w093-0) | 110 | 49 (15 to M47) | 8 | 8 | | [6.2.3 Balanced Trees](https://cracked.guide/guide/knuth-w094-0) | 111 | 33 (01 to M47) | 8 | 9 | | [6.2.4 Multiway Trees](https://cracked.guide/guide/knuth-w095-0) | 112 | 10 (10 to HM37) | 7 | 8 | | [6.3 Digital Searching](https://cracked.guide/guide/knuth-w096-0) | 113 | 45 (00 to M43) | 8 | 8 | | [6.4 Hashing (part 1)](https://cracked.guide/guide/knuth-w097-0) | 114 | 78 (10 to M49) | 8 | 8 | | [6.4 Hashing (part 2)](https://cracked.guide/guide/knuth-w098-0) | 115 | 78 (10 to M49) | 8 | 9 | | [6.5 Retrieval on Secondary Keys](https://cracked.guide/guide/knuth-w099-0) | 116 | 20 (19 to M47) | 7 | 7 | | [Vol 3 review](https://cracked.guide/guide/knuth-w099-1) | 117 | 964 (00 to M50) | 8 | 6 | ## 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 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. ## 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. --- Source: https://cracked.guide/taocp/volume-3 cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.