TAOCP 5.2 Exercise 13

We are given \(N\) records \(R_1,\dots,R_N\) with integer keys \(K_1,\dots,K_N\) satisfying \(u \le K_j \le v\).

taocpmathematicsalgorithmsvolume-3hard

Section 5.2: Internal Sorting

Exercise 13. ▶ [27] Algorithm D requires space for $2N$ records $R_1, \ldots, R_N$ and $S_1, \ldots, S_N$. Show that it is possible to get by with only $N$ records $R_1, \ldots, R_N$, if a new unshuffling procedure is substituted for steps D5 and D6. (Thus the problem is to design an algorithm that rearranges $R_1, \ldots, R_N$ in place, based on the values of $\texttt{COUNT}[0]$, $\ldots$, $\texttt{COUNT}[v]$ after step D4, without using additional memory space; this is essentially a generalization of the problem considered in exercise 10.)

Verified: no
Solve time: 11m17s

Setup

We are given (N) records (R_1,\dots,R_N) with integer keys (K_1,\dots,K_N) satisfying (u \le K_j \le v). After steps D1-D4 of Algorithm D we have an auxiliary array (\texttt{COUNT}[u],\dots,\texttt{COUNT}[v]) where (\texttt{COUNT}[i]) equals the number of keys (\le i); in particular (\texttt{COUNT}[v]=N). The sorted order requires that all records with key (k) occupy the contiguous block of positions [ \texttt{COUNT}[k-1]+1,;\dots,;\texttt{COUNT}[k] ] (with (\texttt{COUNT}[u-1]=0)). The problem is to permute the records (R_1,\dots,R_N) into this order using only the existing (\texttt{COUNT}) array and the record array itself,no extra (O(N)) storage.

Solution

The idea is to follow the cycles of the permutation that sends each record to its final position. In the original Algorithm D this permutation is realised by writing records into a second array (S). To do it in place we simulate the same cycle structure, using the (\texttt{COUNT}) array to find the current target position for a given key. To avoid revisiting records that have already reached their final place, we temporarily mark a record by adding a constant (M = v-u+1) to its key. Because all original keys lie in ([u,v]), a marked key is strictly larger than (v); the original key is recovered by subtracting (M).

Algorithm E (In‑place unshuffling). After step D4 execute the following steps.

E1. [Loop on (j).] For (j = N, N-1, \dots, 1):

  • If (K_j > v) (record already placed), continue with the next (j).
  • Set (i \leftarrow j).

E2. [Follow cycle.]

  • Let (k \leftarrow K_i); if (k > v) then (k \leftarrow k - M).
  • Let (t \leftarrow \texttt{COUNT}[k]).
  • If (t = i):
    The record at position (i) belongs exactly at the current end of its bucket.
    Mark it: (K_i \leftarrow K_i + M).
    Decrement the bucket pointer: (\texttt{COUNT}[k] \leftarrow t-1).
    Go to E1 (next (j)).
  • Else ((t \neq i)):
    Swap (R_i \leftrightarrow R_t).
    The record moved to (t) is now in its final position; mark it: (K_t \leftarrow K_t + M).
    Decrement the bucket pointer: (\texttt{COUNT}[k] \leftarrow t-1).
    (The record that came from (t) is now at (i); it is unmarked.)
    Repeat E2.

E3. [Restore keys.] For (j = 1) to (N): if (K_j > v) then (K_j \leftarrow K_j - M).

After E3 the array (R_1,\dots,R_N) is sorted by key.

Verification

We prove correctness by establishing invariants and showing termination.

Invariants during E1-E2.
At any moment, for each key (k):

  1. (\texttt{COUNT}[k]) equals the largest index of the unfilled positions in the bucket of (k). The filled positions are exactly those that currently hold a marked record with key (k).
  2. Every marked record resides in the bucket corresponding to its (original) key.
  3. The set of unmarked records is exactly the set of records not yet placed in their final bucket.
  4. The permutation mapping each record to its final position decomposes into disjoint cycles. The inner loop (E2) follows one complete cycle: it starts at an unmarked record, repeatedly moves the current record to the target (t = \texttt{COUNT}[k]) (which by invariant 1 is an unfilled, hence unmarked, position), marks that target, and continues with the displaced record. Because the permutation is a product of cycles, the process must eventually return to the starting position (i); at that moment (t = i) and the loop terminates.

Termination.
Each execution of the inner loop marks exactly one previously unmarked record. There are (N) records, so the total number of inner‑loop iterations is at most (N). The outer loop runs (N) times but skips marked records. Hence the algorithm terminates after (O(N)) steps.

Final order.
When the outer loop finishes, all records are marked. By invariant 2 every record lies in the bucket of its key. The buckets are exactly the intervals (\texttt{COUNT}[k-1]+1) to (\texttt{COUNT}[k]) as they were after step D4 (the (\texttt{COUNT}) array was only used as a moving pointer and its final values are irrelevant). Thus the records are grouped by key in nondecreasing order. Step E3 restores the original keys without changing the record order.

Space usage.
The algorithm uses only the (\texttt{COUNT}) array (size (v-u+1)) and the record array (R). The marking constant (M) is a single integer. No additional memory proportional to (N) is required.

Example check.
Take (u=1,v=2,N=4), initial keys ([2,1,2,1]). After D4: (\texttt{COUNT}[1]=2,;\texttt{COUNT}[2]=4). (M=2).

  • (j=4): (K_4=1) unmarked. (i=4), (k=1), (t=2). (t\neq i): swap (R_4\leftrightarrow R_2) (both 1, no change). Mark (R_2): (K_2=3). (\texttt{COUNT}[1]=1).
    (i=4), (k=1), (t=1). (t\neq i): swap (R_4\leftrightarrow R_1) → (R=[1,1,2,2]). Mark (R_1): (K_1=3). (\texttt{COUNT}[1]=0).
    (i=4), (k=2), (t=4). (t=i): mark (R_4): (K_4=4). (\texttt{COUNT}[2]=3).
  • (j=3): (K_3=2) unmarked. (i=3), (k=2), (t=3). (t=i): mark (R_3): (K_3=4). (\texttt{COUNT}[2]=2).
  • (j=2,1): both marked, skipped.
    E3: subtract 2 from marked keys → ([1,1,2,2]). Sorted.

This completes the proof. ∎

Notes

The algorithm is a direct generalization of the cycle‑following method of Exercise 10. There the permutation (p) was given explicitly and its entries were negated to mark visited positions. Here the permutation is defined implicitly by the keys and the (\texttt{COUNT}) array; we use the keys themselves as the marking medium because they are guaranteed to lie in a small range. The constant (M) can be any value larger than (v-u); on a binary computer one could simply use the sign bit if the keys are non‑negative. The procedure is not stable (records with equal keys may change relative order), but stability was not required.