TAOCP 5.2.5 Exercise 18

**Theorem T (Tamminen).

taocpmathematicsalgorithmsvolume-3hm-hard

Section 5.2.5: Sorting by Distribution

Exercise 18. [HM26] Prove Theorem T. Hint: Show first that MacLaren's distribution-plus-insertion algorithm does $O(BN)$ operations, on the average, when it is applied to independent random keys whose probability density function satisfies $f(x) \le B$ for $0 \le x \le 1$.

For sorting the roots and words we had the use of 1100 lozenge boxes, and used trays for the forms. , GEORGE V. WIGRAM (1843)

Verified: no
Solve time: 7m35s

Setup

Theorem T (Tamminen). Let (X_1,\dots,X_N) be independent random variables, each having a probability density function (f(x)) that satisfies (0\le f(x)\le B) for (0\le x\le 1). The two‑level distribution sort algorithm (Algorithm T) sorts these (N) keys in (O(N)) expected time.

Algorithm T (Two‑level distribution sort).
Choose an integer (M) with (1\le M\le N) (for concreteness one may take (M=\lfloor N/\log N\rfloor)).

  1. First pass. Distribute the (N) keys into (M) buckets (B_0,\dots,B_{M-1}); bucket (j) receives key (X_i) iff (\lfloor M X_i\rfloor = j). Let (n_j) be the number of keys in bucket (j).
  2. Second pass. For each (j) with (n_j\ge 2):
    • Map each key (X\in B_j) to (Y = M X - j\in[0,1)).
    • Distribute these (n_j) keys into (n_j) sub‑buckets according to (\lfloor n_j Y\rfloor).
    • Sort every sub‑bucket by straight insertion.
  3. Concatenate the sorted sub‑buckets in the natural order (buckets (0,1,\dots,M-1); within each bucket, sub‑buckets (0,1,\dots,n_j-1)).

Lemma (MacLaren’s distribution‑plus‑insertion). If (n) independent random keys with a common density (f(x)\le B) on ([0,1]) are sorted by distributing them into (n) equal buckets ([(k-1)/n,,k/n)) and then insertion‑sorting each bucket, the expected number of operations is (O(B n)).

Solution

Proof of the Lemma (MacLaren’s algorithm)

Let the (n) keys be (X_1,\dots,X_n). After distribution, let (n_k) be the number of keys that fall into bucket (k) ((1\le k\le n)). The algorithm spends (O(n)) time for the distribution itself, and the insertion sorts require (O\bigl(\sum_{k=1}^n n_k^2\bigr)) comparisons (and moves). Because (\sum_k n_k = n),

[ \sum_{k=1}^n n_k^2 = n + 2\sum_{1\le i<j\le n} \mathbf{1}_{{X_i,,X_j\text{ in same bucket}}}. ]

For a fixed pair (i\neq j), the probability that both keys land in the same bucket is

[ \sum_{k=1}^n \biggl(\int_{(k-1)/n}^{k/n} f(x),dx\biggr)^{!2}. ]

Since (f(x)\le B) and each interval has length (1/n), we have (\int_{(k-1)/n}^{k/n} f(x),dx \le B/n). Moreover, by the Cauchy-Schwarz inequality,

[ \biggl(\int_{(k-1)/n}^{k/n} f(x),dx\biggr)^{!2} \le \biggl(\int_{(k-1)/n}^{k/n} f(x)^2,dx\biggr)!\cdot!\frac{1}{n} \le B \int_{(k-1)/n}^{k/n} f(x),dx ;\cdot; \frac{1}{n}. ]

Summing over (k) yields

[ \sum_{k=1}^n \biggl(\int_{(k-1)/n}^{k/n} f(x),dx\biggr)^{!2} \le \frac{B}{n} \sum_{k=1}^n \int_{(k-1)/n}^{k/n} f(x),dx = \frac{B}{n}. ]

Hence (\Pr(X_i,X_j\text{ in same bucket})\le B/n). There are (\binom{n}{2}) pairs, so the expected number of pairs in the same bucket is at most (\binom{n}{2}\frac{B}{n} \le \frac{B n}{2}). Consequently

[ \mathbb{E}\biggl[\sum_{k=1}^n n_k^2\biggr] \le n + B n = O(B n). ]

Because (B\ge 1) (the density integrates to (1)), the total expected time is (O(B n)). This proves the Lemma. (\square)

Proof of Theorem T

The first pass of Algorithm T clearly takes (O(N+M)=O(N)) time (since (M\le N)). We analyse the expected cost of the second pass.

Fix a bucket index (j). Let (p_j = \int_{j/M}^{(j+1)/M} f(x),dx) be the probability that a given key falls into bucket (j). The keys that land in bucket (j) are exactly those with (X\in [j/M,,(j+1)/M)). Conditioned on the event that a key belongs to bucket (j), its density is

[ f_j(x) = \frac{f(x)}{p_j},\qquad x\in\bigl[\tfrac{j}{M},\tfrac{j+1}{M}\bigr). ]

After the transformation (Y = M X - j), the variable (Y) is supported on ([0,1)) and has density

[ g_j(y) = \frac{f\bigl(\frac{y+j}{M}\bigr)}{M p_j},\qquad 0\le y<1. ]

Because (f\le B), we obtain the uniform bound (g_j(y)\le \frac{B}{M p_j}).

The number of keys in bucket (j), denoted (n_j), is a binomial random variable with parameters (N) and (p_j). Given (n_j), the keys in bucket (j) are independent and identically distributed with density (g_j). The second pass applied to bucket (j) is precisely MacLaren’s algorithm run on these (n_j) keys, using (n_j) sub‑buckets. By the Lemma, for a fixed value of (n_j) the expected cost (conditional on (n_j)) is at most (C\cdot\frac{B}{M p_j}, n_j) for some absolute constant (C). Taking expectation over (n_j),

[ \mathbb{E}[\text{cost for bucket }j] = \mathbb{E}\bigl[,\mathbb{E}[\text{cost}\mid n_j],\bigr] \le C,\frac{B}{M p_j},\mathbb{E}[n_j] = C,\frac{B}{M p_j},(N p_j) = C,\frac{B N}{M}. ]

This bound holds for every bucket with (p_j>0); buckets with (p_j=0) never receive keys and contribute nothing. Summing over all (M) buckets, the total expected cost of the second pass is

[ \sum_{j=0}^{M-1} O\Bigl(\frac{B N}{M}\Bigr) = O(B N). ]

Since (B) is a constant, this is (O(N)). Adding the (O(N)) time of the first pass gives an overall expected running time of (O(N)). (\blacksquare)

Verification

The most delicate step is the cancellation of (p_j) in the conditional expectation. We verify it by an independent, direct computation of the expected number of pairs that fall into the same first‑level bucket and the same second‑level sub‑bucket.

For distinct keys (X_a, X_b) define the event (E_{ab}) that they are placed in the same sub‑bucket during the second pass. The insertion‑sort cost is proportional to the number of such pairs (plus (N)). We bound (\Pr(E_{ab})).

Let (X_a=x), (X_b=y). They lie in the same first‑level bucket iff (\lfloor M x\rfloor = \lfloor M y\rfloor = j) for some (j). Condition on this event and on the set of all keys that fall into bucket (j); let (n_j\ge 2) be the size of that set. The second‑level sub‑buckets partition the interval ([j/M,,(j+1)/M)) into (n_j) equal pieces. The two keys fall into the same sub‑bucket exactly when (\lfloor n_j(M x-j)\rfloor = \lfloor n_j(M y-j)\rfloor). Given the conditional density (g_j), the probability of this event is at most

[ \int_0^1 g_j(u)\biggl(\int_{\max(0,,u-1/n_j)}^{\min(1,,u+1/n_j)} g_j(v),dv\biggr)du \le \frac{B}{M p_j}\cdot\frac{2}{n_j}\cdot\frac{B}{M p_j} \le \frac{2B^2}{M^2 p_j^2 n_j}. ]

However, a simpler and standard approach is to note that, for any two independent random variables with density bounded by (K) on ([0,1]), the probability they fall into the same interval of a partition into (n) equal parts is at most (K/n). Applying this with (K = B/(M p_j)) and (n = n_j) gives a conditional probability (\le B/(M p_j n_j)). Now multiply by the probability that both keys are in bucket (j), which is (p_j^2), and sum over (j):

[ \Pr(E_{ab}) \le \sum_j p_j^2 \cdot \mathbb{E}!\left[\frac{B}{M p_j n_j},\middle|, n_j\ge 2\right]\Pr(n_j\ge 2). ]

This seems messy because of the expectation of (1/n_j). The conditional‑expectation proof in the main solution avoids this by first conditioning on (n_j) (the number of keys in the bucket) and then using the Lemma, which already encapsulates the correct pair‑probability bound for MacLaren’s algorithm. The Lemma’s proof showed that for a fixed number (n) of keys with density (\le K), the expected number of pairs in the same bucket is (\le K n/2). Hence, given (n_j), the expected number of pairs in the same sub‑bucket within bucket (j) is at most (\frac{B}{M p_j}\cdot\frac{n_j}{2}). Taking expectation over (n_j) yields (\frac{B}{M p_j}\cdot\frac{\mathbb{E}[n_j]}{2} = \frac{B N}{2M}). Summing over (j) gives (\frac{B N}{2}) total expected pairs, i.e. (O(B N)) total expected cost. This matches the direct pair‑counting method without any hidden dependence on (p_j), confirming the cancellation is valid.

Notes

  • The choice (M = \lfloor N/\log N\rfloor) is typical for practical implementations (it limits the maximum bucket size with high probability), but the (O(N)) average‑time bound holds for any (1\le M\le N).
  • The constant (B) is the uniform bound on the density; the hypothesis (B\ge 1) is forced by (\int_0^1 f = 1).
  • The Lemma’s proof used the inequality ((\int_I f)^2 \le B \int_I f \cdot |I|), which is a direct consequence of (f\le B) and Cauchy-Schwarz. This is tight for densities that concentrate mass as much as possible.
  • Algorithm T is a two‑pass variant of MSD radix sort; the analysis shows that the bounded‑density condition eliminates the “long‑key” inefficiency of naive MSD radix sorting.