TAOCP Vol 3: Sorting and Searching · Week 87
TAOCP 5.4.4 Reading Tape Backwards: reading guide
Merge patterns that avoid rewinding by reading tapes backward, which flips the order of runs and changes the bookkeeping.
Time About 3 hours this week
Why it matters
Honest note: the tape-merging sections describe hardware nobody uses anymore. Knuth himself says much of 5.4 is historical. The ideas (run generation, merge patterns, minimizing passes over slow storage) still apply to external sorting on disks and SSDs, database sort operators and big-data shuffles, so read for those ideas and skim the tape mechanics.
Before you start
- 5.4.2 The Polyphase Merge
How to approach it
Skim for the idea. Use the spare time on 5.4.1 or on earlier Vol 3 exercises.
Exercises
This is a light section. Skim the exercises, do the ones rated 10 or under in your head, and spend the spare time catching up on earlier exercises you skipped.