TAOCP 5.2.5 Exercise 16

**Algorithm S (Radix list sort for variable‑length strings).

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.5: Sorting by Distribution

Exercise 16. ▶ [25] Design an algorithm to sort strings $\alpha_1, \ldots, \alpha_n$ on an $m$-letter alphabet into lexicographic order. The total running time of your algorithm should be $O(m + n + N)$, where $N = |\alpha_1| + \cdots + |\alpha_n|$ is the total length of all the strings.

Verified: no
Solve time: 22m31s

Solution

Algorithm S (Radix list sort for variable‑length strings).
We are given (n) strings (\alpha_1,\ldots,\alpha_n) over an alphabet of size (m).
Each string is stored in a record with a KEY field and a LINK field.
The total length of all strings is (N=|\alpha_1|+\cdots+|\alpha_n|).
A special sentinel character (\varepsilon) (smaller than every letter of the alphabet) marks the end of a string.
We map letters to integers (1,\ldots,m) and map (\varepsilon) to (0).
The algorithm uses three global structures:

  • PILE_HEAD[0..m] and PILE_TAIL[0..m] - head and tail pointers of piles.
  • A sorted list of used pile indices for the current recursive call.
    This list is maintained with the help of arrays NEXT[0..m], PRED[0..m] and a variable FIRST.
    (All entries are initially Λ; the sorted‑list machinery is explained after the algorithm.)

S1. [Initialize.]
Set PILE_HEAD[i] ← Λ, PILE_TAIL[i] ← Λ for (0\le i\le m).
Initialize the sorted‑list structure (e.g. set FIRST ← Λ).
Let P point to the first record of the input list.

S2. [Sort.]
Call SORT(P, 1).
When the call returns, the records are linked in lexicographic order starting from P.

Subroutine SORT(L, k).
L points to a linked list of records that all share the same prefix of length (k-1).
k is the current digit position (1‑based).

S3. [Trivial list.]
If L = Λ or LINK(L) = Λ, return. (The list is already sorted.)

S4. [Distribute.]
Set C ← L.
While C ≠ Λ do
 NEXT ← LINK(C).
 Let (p = \text{char}(C, k)) (0 if the string has length (<k), otherwise the integer code of the letter).
 If PILE_HEAD[p] = Λ then
  PILE_HEAD[p] ← C, PILE_TAIL[p] ← C,
  insert (p) into the sorted list of used piles (see below).
 Else
  LINK(PILE_TAIL[p]) ← C, PILE_TAIL[p] ← C.
 LINK(C) ← Λ.
 C ← NEXT.

S5. [Output sentinel pile.]
Traverse the sorted list of used piles. For every pile (p=0) (the sentinel), the records in that pile are already linked in the order they were encountered; output them (they are in final position).

S6. [Recurse.]
For every pile (p>0) in the sorted list (in increasing order) call SORT(PILE_HEAD[p], k+1).

S7. [Clean up.]
For every pile (p) in the sorted list, set PILE_HEAD[p] ← Λ, PILE_TAIL[p] ← Λ.
Clear the sorted list for this call (e.g. reset FIRST and mark the used entries as free).

Maintaining the sorted list of used piles.
The array NEXT is used to chain the used piles in increasing order.
When a pile (p) is activated (first string placed into it), we need to insert (p) into the chain.
Because the alphabet is an ordered set ({0,1,\ldots,m}), we can locate the predecessor of (p) in the chain by using an auxiliary structure:

  • Keep an array ACTIVE[0..m] (Boolean) that is cleared only for the current call.
  • To insert (p), set ACTIVE[p] ← 1.
    The predecessor of (p) is the largest (q<p) with ACTIVE[q]=1.
    To find it in amortised constant time, use a disjoint‑set (union‑find) structure on the alphabet, initially each element points to itself.
    When a pile becomes active, we union it with its predecessor; a find operation on (p-1) yields the immediate active predecessor.
    The insertion into the doubly linked list (using NEXT and PRED) is then (O(1)).

After the recursive call returns, the deactivation of the piles is done by traversing the list again and resetting ACTIVE; the union‑find structure can be restored by remembering the modifications on a stack.

The total number of activations over the whole algorithm equals the number of distinct (prefix, character) pairs, which is at most (N).
Hence the amortised cost of maintaining the sorted list is (O(N)).

Analysis of running time.

  • Step S1 initialises the global arrays in (O(m)).
  • Step S4 examines each character of each string exactly once.
    Appending a record to a pile is (O(1)).
    The creation of a new pile (activation) happens at most (N) times in total; the insertion into the sorted list costs (O(1)) amortised.
  • Step S5 outputs the records that have ended; each record is output exactly once.
  • Step S6 makes one recursive call for each non‑empty pile that is not a sentinel.
    The number of such calls is at most (N+1) (each distinct prefix yields at most one call).
    The iteration over the sorted list of used piles for a given call uses time proportional to the number of piles activated in that call, and the sum of those numbers over all calls is (O(N)).
  • Step S7 clears the piles that were used; again the work is proportional to the number of activations, totalling (O(N)).

The time for the initial creation of the linked list (if the records are not already linked) is (O(n)).

Putting everything together, the total running time is

[ O(m)+O(n)+O(N)=O(m+n+N). ]

This completes the proof. ∎