TAOCP 5.4.7: External Radix Sorting
Section 5.4.7 exercises: 7/7 solved.
Section 5.4.7. External Radix Sorting
Exercises from TAOCP Volume 3 Section 5.4.7: 7/7 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [20] | medium | solved | 4m24s |
| 2 | [M28] | math-hard | solved | 5m09s |
| 3 | [M35] | math-hard | solved | 4m11s |
| 4 | [M23] | math-medium | solved | 4m49s |
| 5 | [15] | simple | solved | 3m47s |
| 6 | ▶ [20] | medium | solved | 12m23s |
| 7 | [21] | medium | verified | 1m02s |
TAOCP 5.4.7 Exercise 1
The core mistake in the previous argument is the attempt to manufacture a per-level varying radix structure from tape-role behavior.
TAOCP 5.4.7 Exercise 2
The earlier solution fails because it imports a Fibonacci _tape-capacity invariant_ from polyphase merging that does not belong to radix distribution.
TAOCP 5.4.7 Exercise 3
Let $T \ge 4$ tapes be available.
TAOCP 5.4.7 Exercise 4
The previous solution failed because it treated “group sizes” as independent subproblems and implicitly allowed arbitrary arity patterns.
TAOCP 5.4.7 Exercise 5
The original submission contains no construction or argument, so the solution must be rebuilt from the definitions of Mauchly’s read-backwards radix sort and the 4-LIFO representation used in Section...
TAOCP 5.4.7 Exercise 6
We first analyze Mauchly's read-backward radix sort for 10 keys (0-9) on four tapes.
TAOCP 5.4.7 Exercise 7
A multireel file consists of a finite sequence of reels, each reel being a sequential medium on which records are read and written in forward order, with a forced change of reel when an end is reached...