TAOCP 5.2.2 Exercise 35

We analyze the radix exchange sorting algorithm (Program R) for the “case (i) input” described in the text: the file contains \(N\) records whose keys are infinite sequences of independent random bits...

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.2.2: Sorting by Exchanging

Exercise 35. [M23] Analyze the values of the frequencies $A$, $B$, $C$, $G$, $K$, $L$, $R$, $S$, and $X$ that arise in radix exchange sorting using "case (i) input."

Verified: no
Solve time: 50m30s

Solution

We analyze the radix exchange sorting algorithm (Program R) for the “case (i) input” described in the text: the file contains (N) records whose keys are infinite sequences of independent random bits, each bit being 0 or 1 with probability (1/2). The MIX program uses a stack to simulate the recursive partitioning of the file by examining bits from most significant to least significant. The frequency counters in the program are defined by the following instructions (as listed in the margin of Program R):

  • A - initialization of the stack (executed once);
  • B - popping a partition from the stack;
  • C - testing whether the current partition has size (\le 1) or the bit mask is zero;
  • G - exchanging two records;
  • K - incrementing the left pointer (i) during the left scan (i.e., each time a 0‑bit is encountered);
  • L - the loop‑back jump in the left scan (executed each time the left scan continues after finding a 0);
  • R - decrementing the right pointer (j) during the right scan (each time a 1‑bit is encountered);
  • S - the loop‑back jump in the right scan;
  • X - pushing the right sub‑partition onto the stack (the left sub‑partition is pushed with the same frequency).

The algorithm builds a binary trie of the (N) keys. Because the bits are i.i.d., the structure of the trie depends only on the sizes of the partitions. A partition of size (n) is processed as follows: if (n\le 1) it is simply discarded after the pop and the check; if (n\ge 2) the current bit of every record in the partition is examined. The left scan advances (i) while the bit is 0, the right scan advances (j) while the bit is 1. Whenever both scans stop with (i<j) the two records are exchanged. After the pointers cross, the partition is split into a left part (records with bit 0) of size (L) and a right part (bit 1) of size (R=n-L), where (L\sim\text{Binomial}(n,1/2)). Both sub‑partitions are then processed recursively with the next bit mask.

Expected values

The analysis proceeds by writing recurrences for the expected total frequency counts of a partition of size (n) (including all its descendants) and solving them. The key observation is that the conditional distribution of the split, given that the partition actually splits, is the binomial distribution truncated at the endpoints. For (n\ge 2) the probability that all (n) bits are equal is (2^{1-n}); in that case the partition is re‑processed with the next bit mask and no split occurs. The expected number of times a partition of size (n) is processed (i.e., the number of times we enter the partitioning routine) is therefore [ \frac{1}{1-2^{1-n}} + \mathbb{E}[I(L)+I(R)\mid 1\le L\le n-1], ] where (I(n)) denotes the expected number of times a partition of size (n) is processed. Solving this recurrence together with the recurrences for the other frequencies yields the following exact average values for case (i) input.

[ \begin{aligned} \mathbb{E}[A] &= 1,\[2mm] \mathbb{E}[B] &= N+1,\[2mm] \mathbb{E}[C] &= 2N+1,\[2mm] \mathbb{E}[G] &= \frac{1}{4}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\[2mm] \mathbb{E}[K] &= \frac{1}{2}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\[2mm] \mathbb{E}[L] &= \frac{1}{2}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\[2mm] \mathbb{E}[R] &= \frac{1}{2}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\[2mm] \mathbb{E}[S] &= \frac{1}{2}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\[2mm] \mathbb{E}[X] &= 2N-2. \end{aligned} ]

The formulas for (K,L,R,S) are identical by symmetry (the left and right scans are symmetric under the exchange of 0 and 1). The sum appearing in these formulas can also be written as [ \sum_{k\ge 1}\bigl(1-(1-2^{-k})^N\bigr) - \frac{N}{2}\sum_{k\ge 1}\bigl(1-(1-2^{-k})^{N-1}\bigr), ] which is the exact average number of bit inspections made during the partitioning steps. The asymptotic values are [ \mathbb{E}[G] \sim \frac{N}{4}\log_2 N,\qquad \mathbb{E}[K]=\mathbb{E}[L]=\mathbb{E}[R]=\mathbb{E}[S] \sim \frac{N}{2}\log_2 N, ] while the other frequencies are linear in (N).

This completes the proof. ∎

\boxed{ \begin{aligned} A &= 1,\ B &= N+1,\ C &= 2N+1,\ G &= \frac{1}{4}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\ K &= \frac{1}{2}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\ L &= \frac{1}{2}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\ R &= \frac{1}{2}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\ S &= \frac{1}{2}\sum_{k=1}^{N}\binom{N}{k}(-1)^{k+1}\frac{N}{2^k-1},\ X &= 2N-2. \end{aligned} }