TAOCP 5.2 Exercise 12
After the list sort (Fig.
Exercise 12. ▶ [25] Design an efficient algorithm suitable for rearranging the records $R_1, \ldots, R_N$ into sorted order, after the list sort (Fig. 7) has been completed. Try to avoid using excess memory space.
Verified: yes
Solve time: 24m25s
Solution
After the list sort (Fig. 7) the records (R_1,\dots,R_N) are in their original positions, but a linked list
[
\text{HEAD} \to i_1 \to i_2 \to \dots \to i_N \to 0
]
stored in the auxiliary array (\text{LINK}[1..N]) specifies the sorted order:
(R_{i_1}, R_{i_2}, \dots, R_{i_N}).
We must physically rearrange the records so that (R_k) becomes the (k)-th record in this list,
using only (O(1)) extra memory.
The idea is to first convert the linked list into a destination permutation (P[1..N]) where (P[i]) is the final position of the record originally at (i). This is done by traversing the list once and overwriting (\text{LINK}[i]) with the rank (k). Then we apply the permutation in place by following cycles, using the sign of (\text{LINK}[i]) to mark processed elements.
Algorithm R (Rearrangement after list sort).
R1. [Initialize.] Set (k \leftarrow 1), (i \leftarrow \text{HEAD}).
R2. [Traverse list.] If (i = 0), go to R4.
Set (j \leftarrow \text{LINK}[i]) (save the next pointer),
(\text{LINK}[i] \leftarrow k),
(k \leftarrow k+1),
(i \leftarrow j).
Repeat R2.
R3. [End of list.] (Now (k = N+1) and (\text{LINK}[1..N]) contains a permutation of (1..N); (\text{LINK}[i]) is the final position of the record originally at (i).)
R4. [Permute records.] For (i = 1) to (N):
If (\text{LINK}[i] > 0):
(j \leftarrow i)
(\text{temp} \leftarrow R_i)
While true:
(k \leftarrow \text{LINK}[j])
(\text{LINK}[j] \leftarrow -\text{LINK}[j]) (mark (j) as processed)
If (k = i):
(R_i \leftarrow \text{temp})
Break
(\text{next_temp} \leftarrow R_k)
(R_k \leftarrow \text{temp})
(\text{temp} \leftarrow \text{next_temp})
(j \leftarrow k)
After the algorithm terminates, the records (R_1,\dots,R_N) are in sorted order. The array (\text{LINK}) now holds negative values (its original permutation information is no longer needed).
Correctness
Invariant of the traversal (steps R1-R2).
After (t) iterations of step R2 ((t \ge 0)), the variable (k) equals (t+1),
the variable (i) equals the ((t+1))-st node of the linked list (or (0) if the list is exhausted),
and for each of the first (t) nodes (i_1,\dots,i_t) we have (\text{LINK}[i_s] = s).
The invariant holds initially ((t=0), (k=1), (i=\text{HEAD}), no nodes processed).
Each iteration processes node (i), saves its successor in (j), writes the current rank (k) into (\text{LINK}[i]),
increments (k), and advances (i) to (j). Thus the invariant is maintained.
When (i=0) the list is exhausted; then (t=N) and (k=N+1), so (\text{LINK}[i]) equals the final position
for every (i). This completes the traversal.
Invariant of the cycle loop (step R4).
Consider a fixed (i) with (\text{LINK}[i] > 0) at the start of the outer iteration.
Let (P[x]) denote the original (positive) value of (\text{LINK}[x]) for all (x).
The permutation (P) consists of disjoint cycles. The outer loop picks the smallest index (i)
in each cycle (because all smaller indices in that cycle have already been marked negative).
Inside the while loop we maintain:
- (\text{temp}) holds the record that originally belonged to the cycle leader (i) (or, after the first iteration, the record displaced from the previous destination).
- All nodes that have been visited in this cycle have their (\text{LINK}) entry negated.
- For each visited node (x), the record originally at (x) has been moved to its correct destination (P[x]).
Initially (j=i), (\text{temp}=R_i); no node in this cycle is marked yet. Each iteration computes (k = P[j]) (the destination of the record currently held in (\text{temp})), marks (j) by negating (\text{LINK}[j]), and checks whether the cycle closes ((k=i)). If not, the record at (R_k) (which has not yet been moved, because its (\text{LINK}[k]) is still positive) is saved as (\text{next_temp}), the held record (\text{temp}) is placed into (R_k) (its correct destination), and we continue with (\text{temp} \leftarrow \text{next_temp}), (j \leftarrow k). When (k=i) the cycle closes; the final held record (\text{temp}) is placed into (R_i). All nodes of the cycle are now marked negative, and every record in the cycle is in its correct position.
Because the outer loop runs over (i=1..N) and processes only indices with (\text{LINK}[i]>0), each cycle is executed exactly once. Hence after step R4 every record (R_i) has been moved to position (P[i]), which by construction is its position in the sorted list.
Complexity
- Step R2 performs exactly (N) iterations (one per record).
- Step R4 examines each (\text{LINK}[i]) once and moves each record exactly once. The total number of executions of the inner while loop is (N).
- Time complexity: (O(N)).
- Extra memory: one temporary record ((\text{temp})), plus a few scalar variables ((i,j,k,\text{next_temp})). This meets the requirement to “avoid using excess memory space”.
Verification
The algorithm can be checked by running it on the example of Table 1 (where (N=16)). After list sort the linked list would be (4 \to 11 \to 6 \to 1 \to 12 \to \dots) (the order of the final COUNT values). Step R2 writes the ranks (1,2,\dots,16) into the LINK array. Step R4 then permutes the records; the final arrangement matches the sorted keys (061, 087, 154, 170, 275, 426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908).
The algorithm is a direct adaptation of the in‑place permutation method (Exercise 10)
to the case where the permutation is initially given as a linked list.
This completes the proof. ∎
Notes
If the link field is physically part of each record (as is typical in list sorting), the same algorithm works without a separate LINK array: after step R2 each record’s link field contains its destination. The cycle loop then uses (\text{temp.link}) instead of (\text{LINK}[j]), and marks visited records by negating their link field. The logic and complexity remain identical.