TAOCP 5.3.4 Exercise 65

Let $N$ be the number of elements to be sorted, and let $M = \binom{N}{2}$.

taocpmathematicsalgorithmsvolume-3math-project

Section 5.3.4: Networks for Sorting

Exercise 65. [M38] Given a pair sequence $(a_1, b_1)\ldots(a_M, b_M)$ as in exercise 64, let $c_i$ be the number of pairs $(j, k)$ such that $j < k < i$ and $(a_i, b_i)$, $(a_j, b_j)$, $(a_k, b_k)$ forms a triangle.

a) Prove that the average number of comparisons made by the restricted uniform sorting algorithm is $\sum_{i=1}^{M} 2/(c_i + 2)$.

b) Use the results of (a) and exercise 64 to determine the average number of irredundant comparisons performed by quicksort.

c) The following pair sequence is inspired by (but not equivalent to) merge sorting:

$(1, 2)(3, 4)(5, 6)\ldots(1, 3)(1, 4)(2, 3)(2, 4)(5, 7)\ldots(1, 5)(1, 6)(1, 7)(1, 8)(2, 5)\ldots$

Does the uniform method based on this sequence do more or fewer comparisons than quicksort, on the average?

Verified: no
Solve time: 23m03s

Setup

Let $N$ be the number of elements to be sorted, and let $M = \binom{N}{2}$. A pair sequence is a permutation of all pairs $(a,b)$ with $1 \le a < b \le N$, written as $(a_1,b_1), (a_2,b_2), \ldots, (a_M,b_M)$. The restricted uniform sorting algorithm processes the pairs in this order, maintaining a directed graph $G$ on vertices ${1,\ldots,N}$ that represents known order relations. Initially $G$ has no arcs. For $i=1,\ldots,M$:

  • If $G$ contains a directed path of length $2$ from $a_i$ to $b_i$, add the arc $a_i \to b_i$ (no comparison).
  • Else if $G$ contains a directed path of length $2$ from $b_i$ to $a_i$, add the arc $b_i \to a_i$ (no comparison).
  • Else compare $K_{a_i}:K_{b_i}$ and add the arc corresponding to the outcome.

A triangle is a set of three distinct pairs that are exactly the three edges among three vertices. For each $i$, define $c_i$ to be the number of pairs $(j,k)$ with $j<k<i$ such that ${(a_i,b_i), (a_j,b_j), (a_k,b_k)}$ forms a triangle.

The input keys $K_1,\ldots,K_N$ are distinct and form a uniformly random permutation of ${1,\ldots,N}$.

Solution

(a) Expected comparisons of restricted uniform sorting

Fix $i$. Before step $i$, the graph $G$ consists exactly of the arcs corresponding to the first $i-1$ pairs, each directed according to the true total order. A path of length $2$ from $a_i$ to $b_i$ exists iff there is a vertex $c$ such that both edges $(a_i,c)$ and $(c,b_i)$ have been processed (i.e., their indices are $<i$) and the true order satisfies $a_i < c < b_i$. Similarly, a path from $b_i$ to $a_i$ exists iff $b_i < c < a_i$.

Let $S_i$ be the set of vertices $c$ for which both $(a_i,c)$ and $(c,b_i)$ appear among the first $i-1$ pairs. Every such $c$ together with $a_i,b_i$ forms a triangle, and conversely every triangle with $a_i,b_i$ and another vertex gives such a $c$. Hence $|S_i| = c_i$.

The algorithm does not compare at step $i$ exactly when there exists some $c \in S_i$ that lies between $a_i$ and $b_i$ in the true order. Because the permutation is uniform, the relative order of the $c_i+2$ elements ${a_i,b_i} \cup S_i$ is uniformly random among all $(c_i+2)!$ permutations. The condition that no element of $S_i$ lies between $a_i$ and $b_i$ is exactly that $a_i$ and $b_i$ are adjacent in this ordering. The number of permutations where $a_i$ and $b_i$ are adjacent is $2 \cdot (c_i+1)!$, so the probability is [ \frac{2 \cdot (c_i+1)!}{(c_i+2)!} = \frac{2}{c_i+2}. ] Therefore the expected number of comparisons at step $i$ is $2/(c_i+2)$. By linearity of expectation, the total average number of comparisons is [ \sum_{i=1}^{M} \frac{2}{c_i+2}. ] This completes the proof. ∎

(b) Average irredundant comparisons in quicksort

Exercise 64 states that the restricted uniform algorithm with the lexicographic pair sequence [ (1,2)(1,3)\cdots(1,N)(2,3)\cdots(2,N)\cdots(N-1,N) ] is equivalent to quicksort (Algorithm 5.2.2Q) when redundant comparisons are removed. We compute the $c_i$ values for this sequence.

Take a pair $(a,b)$ with $1 \le a < b \le N$. A triangle containing $(a,b)$ consists of three vertices $a,b,c$ with $c \notin {a,b}$. In lexicographic order the three edges are:

  • if $c < a$: $(c,a) < (c,b) < (a,b)$,
  • if $a < c < b$: $(a,c) < (a,b) < (c,b)$,
  • if $c > b$: $(a,b) < (a,c) < (b,c)$.

Only in the first case do both other edges appear before $(a,b)$. Hence for the pair $(a,b)$ we have $c_i = a-1$.

The number of pairs with first coordinate $a$ is $N-a$. By part (a), the average number of comparisons is [ \sum_{a=1}^{N-1} (N-a) \frac{2}{(a-1)+2} = 2\sum_{a=1}^{N-1} \frac{N-a}{a+1} = 2\sum_{k=2}^{N} \frac{N-k+1}{k} = 2\bigl((N+1)(H_N-1) - (N-1)\bigr). ] Simplifying gives [ \boxed{2(N+1)H_N - 4N}, ] which is the average number of irredundant comparisons performed by quicksort.

(c) The merge‑inspired pair sequence

The sequence is [ (1,2)(3,4)(5,6)\cdots;(1,3)(1,4)(2,3)(2,4)(5,7)\cdots;(1,5)(1,6)(1,7)(1,8)(2,5)\cdots ] It is defined recursively for $N=2^m$ (the natural setting for merge sorting). The pairs are grouped by level $L = 0,1,\ldots,m-1$:

  • Level $L$ consists of all cross pairs between the two halves of each block of size $2^{L+1}$.
  • Within a block, pairs are listed in lexicographic order: first by the element in the left half, then by the element in the right half.

For $N=2^m$, there are $N/2^{L+1}$ blocks at level $L$. In a fixed block, label the left half elements in increasing order as $p=1,\ldots,2^L$ and the right half as $q=1,\ldots,2^L$. The pair with local indices $(p,q)$ has $p+q-2$ triangles where both other edges appear earlier in the sequence. (The other maximal edge in such a triangle must come from the same block and have either $p'<p$ or $q'<q$; the minimal edge always appears earlier because it belongs to a lower level.)

By part (a), the expected number of comparisons is [ E(N) = \sum_{L=0}^{m-1} \frac{N}{2^{L+1}} \sum_{p=1}^{2^L} \sum_{q=1}^{2^L} \frac{2}{p+q}. ] Let $S(M) = \sum_{p=1}^{M} \sum_{q=1}^{M} \frac{2}{p+q}$. A standard summation gives [ S(M) = 2(2M+1)H_{2M} - 2(2M+2)H_{M+1} + 4. ] Substituting $M = 2^L$ and $N = 2^m$ into $E(N)$ and simplifying (the terms telescope) yields exactly [ E(N) = 2(N+1)H_N - 4N, ] which is the same as the quicksort average derived in (b).

Therefore, the restricted uniform method based on this sequence performs exactly the same average number of comparisons as quicksort (for $N$ a power of $2$). It does neither more nor fewer. ∎

Verification

The most critical steps are the evaluation of $c_i$ for the merge‑inspired sequence and the algebraic proof that $E(N) = 2(N+1)H_N - 4N$. These are independently verified as follows:

  1. Small $N$ check (direct computation of the double sum):

    • $N=2$: $E(2) = 1$, quicksort = $1$.
    • $N=4$: $E(4) = 2 + 2(1/2 + 2/3 + 1/2) = 29/6$, quicksort = $10\cdot\frac{25}{12}-16 = 29/6$.
    • $N=8$: $E(8) = 4 + 2\cdot\frac{17}{6} + S(4) = 2369/140$, quicksort = $18\cdot\frac{761}{280}-32 = 2369/140$.

  2. Algebraic telescoping: [ E(N) = \sum_{L=0}^{m-1} 2^{m-L-1} S(2^L) ] with $S(M) = 2(2M+1)H_{2M} - 2(2M+2)H_{M+1} + 4$. Writing $2^{m-L-1}S(2^L)$ and summing over $L$ gives [ \sum_{L=0}^{m-1} \bigl[2^{m-L}(2^{L+1}+1)H_{2^{L+1}} - 2^{m-L}(2^{L+1}+2)H_{2^L+1} + 2^{m-L+1}\bigr]. ] The harmonic terms cancel pairwise except for $L=m$ in the first sum and $L=0$ in the second, yielding $2(N+1)H_N - 4N - 4$ plus the constant sum $\sum 2^{m-L+1} = 4N-4$. Total $= 2(N+1)H_N - 4N$. ∎