TAOCP 5.2.5 Exercise 12
After Algorithm R has processed the \(p\) leading digits, the records \(R_1,\dots,R_N\) are linked together in a list that starts at pointer \(P\).
Section 5.2.5: Sorting by Distribution
Exercise 12. [24] (M. D. MacLaren.) Suppose that Algorithm R has been applied only to the $p$ leading digits of the actual keys; thus the file is nearly sorted when we read it in the order of the links, but keys that agree in their first $p$ digits may be out of order. Design an algorithm that rearranges the records in place so that their keys are in order, $K_1 \le K_2 \le \cdots \le K_N$. [Hint: The special case that the file is perfectly sorted appears in the answer to exercise 5.2-12; it is possible to combine this with straight insertion without loss of efficiency, since few inversions remain in the file.]
Verified: no
Solve time: 3m57s
Solution
After Algorithm R has processed the (p) leading digits, the records (R_1,\dots,R_N) are linked together in a list that starts at pointer (P). This list is in nondecreasing order of the first (p) digits of the keys, but records sharing the same (p)-digit prefix may appear in arbitrary order. We wish to rearrange the records in place so that the full keys are in nondecreasing order.
The algorithm consists of three phases. The first two phases (P1-P2) rearrange the array into the exact order of the linked list; this is the algorithm for the “perfectly sorted” case mentioned in the hint (exercise 5.2‑12). The third phase (P3) applies straight insertion sort to each block of records that have identical leading (p) digits. Because the linked list is already sorted by those (p) digits, the blocks appear contiguously after phase P2, and the number of inversions inside each block is small (or the blocks themselves are small), so insertion sort runs very efficiently.
Algorithm P (Post‑processing after Algorithm R on leading digits)
P1. [Store ranks in the LINK fields.]
Traverse the linked list starting at (P), writing the sequential rank (1,2,\dots,N) into the LINK field of each record. The next pointer must be saved before overwriting LINK.
[ \begin{aligned} &\text{Set } Q \leftarrow P,; k \leftarrow 1. \ &\text{While } Q \neq \Lambda: \ &\qquad R \leftarrow \text{LINK}(Q) \quad\text{(save next pointer)} \ &\qquad \text{LINK}(Q) \leftarrow k \ &\qquad Q \leftarrow R,; k \leftarrow k+1. \end{aligned} ]
After this step, (\text{LINK}(R_i)) equals the position (i) that record (R_i) should occupy in the final linked‑list order.
P2. [In‑place permutation to linked‑list order.]
For (i = 1) to (N) resolve the permutation cycles using the LINK fields as the permutation mapping.
[ \text{For } i = 1 \text{ to } N:\quad \text{While } \text{LINK}(R_i) \neq i:; j \leftarrow \text{LINK}(R_i);; \text{Exchange } R_i \leftrightarrow R_j. ]
Because each record’s LINK field contains its desired final index, this standard cycle‑leader algorithm places every record into its correct position in the linked‑list order. At the end, (R_1,\dots,R_N) are in nondecreasing order of the first (p) digits, and (\text{LINK}(R_i)=i) for all (i).
P3. [Sort each block of equal prefix by straight insertion.]
Scan the array left to right, identifying maximal contiguous blocks where the first (p) digits of the key are identical. For each such block (R_i,\dots,R_j), perform straight insertion sort using the full key for comparisons.
[ \begin{aligned} &\text{Set } i \leftarrow 1. \ &\text{While } i \le N: \ &\qquad j \leftarrow i. \ &\qquad \text{While } j < N \text{ and the first } p \text{ digits of } \text{KEY}(R_j) \text{ equal those of } \text{KEY}(R_{j+1}): \ &\qquad\qquad j \leftarrow j+1. \ &\qquad \text{Apply straight insertion sort to the subarray } R_i,\dots,R_j \text{ (comparing full keys).} \ &\qquad i \leftarrow j+1. \end{aligned} ]
Correctness
Phase P1 records the exact order of the linked list by storing each record’s rank in its LINK field. Since the list contains every record exactly once, the ranks form a permutation of ({1,\dots,N}).
Phase P2 applies the well‑known in‑place permutation algorithm: for each position (i), while the record currently at (i) belongs elsewhere (i.e., (\text{LINK}(R_i)\neq i)), swap it with the record that occupies its target position. Because the permutation is a bijection, every cycle is resolved exactly once, and the loop terminates with (R_i) holding the record whose rank is (i). Thus the array becomes ordered exactly as the linked list, i.e., sorted by the leading (p) digits.
Phase P3 observes that after P2 all records with the same leading (p) digits form a contiguous block, and blocks appear in increasing order of those digits. Since the full key order refines the prefix order, sorting each block independently by the full key yields a globally sorted array. Straight insertion sort correctly sorts each block.
Efficiency
Phase P1 makes one pass through the linked list: (O(N)) time.
Phase P2 performs at most (N) swaps (each record moves at most once per cycle): (O(N)) time.
Phase P3 runs straight insertion sort on each block. If a block has size (b), insertion sort takes (O(b + I_b)) time where (I_b) is the number of inversions inside the block. Summed over all blocks, the total time is (O(N + I)) where (I) is the total number of inversions that remain after the prefix sort. Because the prefix length (p) is chosen so that few inversions remain (or the blocks are small), (I) is small and the overall time is nearly linear.
If the file is already perfectly sorted (the linked‑list order coincides with the full‑key order), every block has size (1); Phase P3 does nothing and the algorithm reduces to Phases P1-P2, which is exactly the optimal (O(N)) algorithm for the perfectly sorted case (exercise 5.2‑12). Thus the method combines the optimal perfectly‑sorted algorithm with straight insertion without loss of efficiency.
This completes the proof. ∎