TAOCP 5.2.5 Exercise 10

We consider the same record structure as in Algorithm R (Section 5.

taocpmathematicsalgorithmsvolume-3hard

Section 5.2.5: Sorting by Distribution

Exercise 10. [30] Design an efficient most-significant-digit-first radix-sorting algorithm that uses linked memory. (As the size of the subfiles decreases, it is wise to decrease $M$, and to use a nonradix method on the really short subfiles.)

Verified: no
Solve time: 13m58s

Setup

We consider the same record structure as in Algorithm R (Section 5.2.5). There are (N) records (R_1,\dots,R_N), each containing a LINK field (a pointer). The key of a record is a (p)-tuple ((a_1,a_2,\dots,a_p)) with (0\le a_i < M_i), where (M_i) is the radix used for the (i)-th digit. The order is lexicographic: ((a_1,\dots,a_p) < (b_1,\dots,b_p)) iff for some (j) we have (a_i=b_i) for all (i<j) and (a_j<b_j). We assume a function (\text{digit}(P,d)) that returns the (d)-th digit of the key in the record pointed to by (P).

We choose a threshold (T) (e.g. (T=10) or (20)) such that subfiles of size (\le T) are sorted by a simple non‑radix method (insertion sort on the linked list). The radices (M_1,M_2,\dots,M_p) are chosen in advance with (M_1\ge M_2\ge\cdots\ge M_p); as the subfiles become smaller we use smaller radices, and when (M_d\le T) we may simply stop the radix process and switch to insertion sort.

We allocate an array of header nodes (\text{HEADER}[0\dots M_{\max}-1]) where (M_{\max}=M_1). For each header we maintain two pointers: [ \text{BOTM}[i] = \text{LINK}(\text{HEADER}[i])\quad\text{(first element of pile (i))},\qquad \text{TOP}[i]\quad\text{(last element of pile (i))}. ] A pile is empty iff (\text{BOTM}[i]=\Lambda). Initially (\text{TOP}[i]=\text{HEADER}[i]) and (\text{BOTM}[i]=\Lambda).

We also maintain a stack (\text{STACK}) whose entries are quadruples ((\text{HEAD},\text{TAIL},d,n)) representing a linked list from (\text{HEAD}) to (\text{TAIL}) of (n) records that all share the same prefix of length (d-1) (i.e. their first (d-1) digits are identical). The stack is ordered so that the entry on top has the lexicographically smallest prefix.

Two global pointers (\text{OUT_HEAD}) and (\text{OUT_TAIL}) denote the head and tail of the fully sorted output list (initially (\Lambda)).

Solution

Algorithm M (MSD radix list sort)

M1. [Initialize.] Link all records in their original order:
for (j=1) to (N-1): (\text{LINK}(R_j)\leftarrow\text{LOC}(R_{j+1}));
(\text{LINK}(R_N)\leftarrow\Lambda).
Set (\text{OUT_HEAD}\leftarrow\Lambda,;\text{OUT_TAIL}\leftarrow\Lambda).
If (N>0), push ((\text{LOC}(R_1),\text{LOC}(R_N),1,N)) onto (\text{STACK}).

M2. [Stack empty?] If (\text{STACK}) is empty, go to M9.

M3. [Pop.] Pop ((\text{HEAD},\text{TAIL},d,n)) from (\text{STACK}).

M4. [All digits processed?] If (d>p), the subfile is completely sorted (all keys equal). Go to M8.

M5. [Trivial subfile?] If (n=1), a single record is already sorted. Go to M8.

M6. [Small subfile?] If (n\le T), sort the subfile from (\text{HEAD}) to (\text{TAIL}) using Algorithm I (insertion sort on linked list). Go to M8.

M7. [Distribute.] Let (M\leftarrow M_d).
For (i=0) to (M-1): set (\text{TOP}[i]\leftarrow\text{HEADER}[i]), (\text{LINK}(\text{HEADER}[i])\leftarrow\Lambda).
Set (P\leftarrow\text{HEAD}). Initialize (\text{COUNT}[0\dots M-1]\leftarrow 0).
 Loop:
  (i\leftarrow\text{digit}(P,d)).
  (\text{LINK}(\text{TOP}[i])\leftarrow P); (\text{TOP}[i]\leftarrow P).
  (\text{COUNT}[i]\leftarrow\text{COUNT}[i]+1).
  If (P=\text{TAIL}), exit loop.
  (P\leftarrow\text{LINK}(P)).
For (i=M-1) down to (0):
 If (\text{LINK}(\text{HEADER}[i])\neq\Lambda), push ((\text{LINK}(\text{HEADER}[i]),\text{TOP}[i],d+1,\text{COUNT}[i])) onto (\text{STACK}).
Go to M2.

M8. [Append sorted subfile.] The subfile from (\text{HEAD}) to (\text{TAIL}) is fully sorted.
If (\text{OUT_TAIL}=\Lambda), set (\text{OUT_HEAD}\leftarrow\text{HEAD}); else set (\text{LINK}(\text{OUT_TAIL})\leftarrow\text{HEAD}).
Set (\text{OUT_TAIL}\leftarrow\text{TAIL}). Go to M2.

M9. [Terminate.] The sorted list begins at (\text{OUT_HEAD}), and (\text{LINK}(\text{OUT_TAIL})=\Lambda). ■

Algorithm I (Insertion sort on a linked list)

Input: (\text{HEAD},\text{TAIL}) of a linked list of size (n) ((2\le n\le T)).
Output: The same list, sorted in place; new (\text{HEAD},\text{TAIL}) are the endpoints of the sorted list.

I1. (\text{SORTED_HEAD}\leftarrow\Lambda,;\text{SORTED_TAIL}\leftarrow\Lambda).
(P\leftarrow\text{HEAD}).

I2. While (P\neq\Lambda):
 (Q\leftarrow P;; P\leftarrow\text{LINK}(P);; \text{LINK}(Q)\leftarrow\Lambda). (Detach (Q).)
 If (\text{SORTED_HEAD}=\Lambda):
  (\text{SORTED_HEAD}\leftarrow Q;;\text{SORTED_TAIL}\leftarrow Q).
 Else:
  Find the last record (R) in the sorted list such that (\text{KEY}(R)\le\text{KEY}(Q)) (lexicographic comparison).
  If no such (R) (i.e. (\text{KEY}(Q)<\text{KEY}(\text{SORTED_HEAD}))):
   Insert (Q) at front: (\text{LINK}(Q)\leftarrow\text{SORTED_HEAD};;\text{SORTED_HEAD}\leftarrow Q).
  Else if (R=\text{SORTED_TAIL}):
   Insert (Q) at end: (\text{LINK}(R)\leftarrow Q;;\text{SORTED_TAIL}\leftarrow Q).
  Else:
   Insert (Q) after (R): (\text{LINK}(Q)\leftarrow\text{LINK}(R);;\text{LINK}(R)\leftarrow Q).

I3. Set (\text{HEAD}\leftarrow\text{SORTED_HEAD},;\text{TAIL}\leftarrow\text{SORTED_TAIL}). ■

Verification

We prove correctness by establishing three invariants that hold at the start of each iteration of the main loop (step M2).

Invariant 1 (Output list). The list from (\text{OUT_HEAD}) to (\text{OUT_TAIL}) is sorted in strictly increasing lexicographic order and contains exactly the records that have been completely processed (i.e. removed from the stack and never pushed back).

Invariant 2 (Stack). Every entry ((\text{HEAD},\text{TAIL},d,n)) on the stack satisfies:

  • The linked list from (\text{HEAD}) to (\text{TAIL}) contains exactly (n) records.
  • All records in this list have identical keys in positions (1,\dots,d-1).
  • If we read the stack from top to bottom, the common prefixes of the entries are in strictly increasing lexicographic order.

Invariant 3 (Partition). The sets of records in the output list and in all stack entries form a partition of the original (N) records (no overlap, none missing).

Initialization. After M1, the output list is empty. The stack contains one entry with all (N) records, (d=1), and the empty prefix (vacuously identical). All three invariants hold.

Maintenance. Consider the entry popped in M3.

  • Case (d>p) (M4): All (p) digits are equal, so the subfile is already sorted. Appending it to the output list preserves Invariant 1 because, by Invariant 2, its prefix is larger than every prefix already in the output list and smaller than every prefix remaining on the stack. Invariant 3 holds because the records move from stack to output.

  • Case (n=1) (M5): A single record is trivially sorted; the same reasoning applies.

  • Case (n\le T) (M6): Algorithm I sorts the subfile by the remaining digits (d,\dots,p). Since the prefix of length (d-1) is fixed, sorting by the full key is equivalent to sorting by the suffix. Insertion sort is stable (it inserts after the last record with an equal key), so the relative order of records with identical keys is preserved. The sorted subfile is appended to the output list; the stack order invariant guarantees its prefix lies between the output list and the remaining stack entries.

  • Case distribution (M7): The subfile is split into (M) queues according to digit (d). Because all records share the same prefix of length (d-1), each queue corresponds to a distinct prefix of length (d). The queues are pushed onto the stack in reverse order ((M-1) down to (0)), so the smallest new prefix ends up on top. This preserves Invariant 2. The total number of records is conserved (Invariant 3), and the output list is unchanged (Invariant 1).

Termination. Each distribution increases (d) by 1. Since (d\le p+1) and we stop distributing when (d>p) or (n\le T), the maximum depth is (p). The stack size is bounded because every distribution replaces one entry with at most (M) entries whose sizes sum to the original size; the process stops when all entries have size (\le T) or (d>p). Eventually the stack becomes empty and the algorithm terminates at M9.

Stability. The distribution step traverses the subfile from (\text{HEAD}) to (\text{TAIL}), appending each record to the tail of its queue. This preserves the order of records with the same digit. The initial list is in the original order, and Algorithm I is stable. Therefore the overall algorithm is stable.

Boundary cases.

  • (N=0): stack empty initially, output list empty.
  • All keys equal: after the first distribution all records go to one queue; (d) increases until (d>p), then the subfile is appended.
  • Subfile size exactly (T): insertion sort is used.
  • Subfile size (1): handled directly without insertion sort.

Complexity.
Let (p) be the number of digits and (T) the threshold. Each record participates in at most (p) distribution steps, each doing (O(1)) work. The total work for insertion sort is (\sum n_i^2) over all small subfiles; since each (n_i\le T) and (\sum n_i\le N), this sum is (\le TN). Hence total time is (O(pN + TN) = O(pN)) for constant (T).
Space: (N) records, (M_{\max}) header nodes, and a stack of size at most (N) (can be reduced by not pushing subfiles of size (1)).

This completes the proof. ∎

Notes

  1. Choice of radices (M_d). A good practical strategy is to start with a large radix (e.g. (M_1=256)) and decrease it geometrically (e.g. (M_{d+1}\approx\sqrt{M_d}) or (M_{d+1}=M_d/4)) until (M_d\le T). The product (\prod M_d) must cover the key range. If keys are (b)-bit integers, one can simply take (M_d=2^{r_d}) with decreasing (r_d).

  2. Threshold (T). Typical values are (10)-(30). The optimal (T) depends on the relative speed of the radix distribution versus the insertion sort inner loop.

  3. Stack implementation. The stack can be a simple array of size (N) (or a linked list). Since we push at most (M) entries per distribution, the maximum stack depth is (p) but the total number of entries ever pushed can be as large as (N) (when all keys are distinct). To limit the stack size, one can immediately append subfiles of size (1) (step M5) without pushing them.

  4. Alternative: breadth‑first processing. Instead of a stack, a queue can be used for breadth‑first MSD radix sort. The invariants change slightly, but the algorithm remains correct. Depth‑first with a stack is usually more cache‑friendly because it finishes small subfiles completely before moving on.

  5. Relation to Algorithm R. Algorithm R is an LSD radix sort that uses the same queue structure (Algorithm H). Algorithm M uses the same distribution mechanism but processes digits from most significant to least, recursing (via the stack) on each non‑empty pile. The hooking‑up step (Algorithm H) is not needed because the stack implicitly manages the concatenation order.