Week 86 of 125
TAOCP 5.4.2 and 5.4.3
Sign up or sign in to tick these off and give this week a due date.
-
A way to merge runs using a limited number of tapes without wasting passes, where the ideal initial run distribution follows generalized Fibonacci numbers.
Time About 5 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.1 Multiway Merging
- 1.2.8 Fibonacci Numbers
How to approach it
Simulate a 3-tape polyphase merge by hand to see the Fibonacci pattern. Skim the detailed tape-handling algorithms.
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.
Traps
- Spending a lot of time on tape rewind details.
-
Another tape-merge pattern that cascades merges of decreasing order, and how it compares to polyphase.
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. Note how it compares to polyphase and move on.
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.