TAOCP 5.4 Exercise 1
The internal sorting phase creates initial runs of length \(M\), where \(M\) is the number of records that fit in internal memory.
Exercise 1. [15] The text suggests internal sorting first, followed by external merging. Why don’t we do away with the internal sorting phase, simply merging the records into longer and longer runs right from the start?
Verified: no
Solve time: 19s
Solution
The internal sorting phase creates initial runs of length (M), where (M) is the number of records that fit in internal memory. If we omitted this phase and started merging from runs of length (1) (each individual record is trivially a sorted run), the number of merge passes required would be (\lceil \lg N \rceil) for (N) total records, since each pass doubles the run length. With internal sorting, the number of merge passes is reduced to (\lceil \lg(N/M) \rceil).
Each merge pass reads and writes the entire file, so the total amount of tape I/O is proportional to the number of passes. For the example in the text ((N = 5\times 10^6), (M = 10^6)), internal sorting yields (\lceil \lg 5 \rceil = 3) passes, whereas starting from length‑1 runs would require (\lceil \lg 5\times 10^6 \rceil \approx 23) passes,nearly eight times more I/O.
Moreover, internal sorting is performed entirely in fast memory, without any tape motion, so it is orders of magnitude faster per record than external merging. Eliminating the internal sorting phase would therefore drastically increase the running time.
\boxed{\text{Internal sorting produces long initial runs in fast memory, reducing the number of external merge passes from } \lceil \lg N \rceil \text{ to } \lceil \lg(N/M) \rceil \text{ and avoiding I/O for the initial sort.}}
This completes the proof. ∎