TAOCP 5.2.1 Exercise 17

Section 5.2.1: Sorting by Insertion

Exercise 17. [M21] Show that, when $N = 2^t$ and $h_s = 2^s$ for $t > s \ge 0$, there is a unique permutation of ${1, 2, \ldots, N}$ that maximizes the number of move operations performed by Algorithm D. Find a simple way to describe this permutation.

Verified: no
Solve time: 9m01s

Solution

We consider Shellsort (Algorithm D) with $N = 2^t$ and increments $h_s = 2^s$ for $s = t-1, t-2, \ldots, 0$.
A move operation is one execution of step D5, which shifts an element one position during straight insertion.
When a list of length $m$ is sorted by straight insertion, the number of moves equals the number of inversions in that list.

Structure of the passes

For a given $s$, the increment is $h = 2^s$. The array is partitioned into $2^s$ independent subarrays $$ A_{s,i} = {, i,; i+h,; i+2h,; \ldots,; i+(2^{t-s}-1)h ,}, \qquad i = 1,\ldots,2^s, $$ each of length $2^{t-s}$. During pass $s$ each $A_{s,i}$ is sorted by straight insertion; the number of moves in this pass is the total number of inversions within the $A_{s,i}$ before the pass begins.

After pass $s$ the array becomes $h$-ordered: $K_i \le K_{i+h}$ for all $i \le N-h$.

Analysing a merge step

For $s \ge 1$, pass $s-1$ works with increment $h/2 = 2^{s-1}$. Each of its subarrays has length $2^{t-s+1}$ and is formed by interleaving two consecutive sorted subarrays from pass $s$.
Let these two sorted lists be $$ L = (L_1 \le L_2 \le \cdots \le L_m),\qquad R = (R_1 \le R_2 \le \cdots \le R_m), \quad m = 2^{t-s}. $$ The interleaved array before pass $s-1$ is $$ L_1,; R_1,; L_2,; R_2,; \ldots,; L_m,; R_m. $$ The number of moves required to sort this array by straight insertion is exactly the number of its inversions. Because $L$ and $R$ are sorted, every inversion is of the form $(L_i, R_j)$ with $i \le j$ and $L_i > R_j$. The maximum possible number of such inversions is $m(m+1)/2$, attained iff the smallest element of $L$ exceeds the largest element of $R$, i.e. $L_1 > R_m$. When this condition holds, the number of inversions is $m(m+1)/2$ independently of the internal order of $L$ and $R$.

Base case ($s = t-1$)

Here $h = 2^{t-1}$ and the subarrays have length $2$: $$ A_{t-1,i} = {i,; i+2^{t-1}},\quad i=1,\ldots,2^{t-1}. $$ Each such subarray is sorted by one comparison. The number of moves is $1$ if the first element is larger than the second, and $0$ otherwise. To maximise the moves in this pass we must have $$ K_i > K_{i+2^{t-1}} \qquad\text{for all } i=1,\ldots,2^{t-1}. $$ This is exactly the condition “all elements of the left half (MSB $=0$) are larger than all elements of the right half (MSB $=1$)” inside every pair with the same lower bits.

Inductive maximisation

Suppose the moves in passes $t-1, t-2, \ldots, s$ have been maximised. Then every subarray of pass $s$ is sorted, and the condition “left subarray $>$ right subarray” holds at all levels down to the base. To maximise pass $s-1$ we must additionally have $L_1 > R_m$ for every merge, i.e. all elements of the left subarray must be larger than all elements of the right subarray.

Proceeding inductively, the total number of moves is maximised if and only if at every level of the binary tree defined by the recursive odd/even splits (the most significant bit down to the least significant bit) all elements of the left child are larger than all elements of the right child.

The unique order

This condition imposes a unique total order on the positions $1,\ldots,N$.
Let $i-1$ and $j-1$ be the $0$-based indices, written as $t$-bit binary numbers. Let $k$ be the most significant bit where they differ. The condition says: the position with bit $k = 0$ must receive a larger value than the position with bit $k = 1$.

Equivalently, if we list the indices $0,1,\ldots,N-1$ in the order of their bit‑reversal (reversing the $t$-bit binary representation), the largest value $N$ goes to the index with bit‑reversal $0$, the next largest to the index with bit‑reversal $1$, and so on.
Denote by $\rho_t(x)$ the bit‑reversal of the $t$-bit integer $x$. Then the unique worst‑case permutation is $$ K_i = N - \rho_t(i-1) \qquad (1 \le i \le N). $$ In words: write the numbers $N, N-1, \ldots, 1$ into the array in the order of the bit‑reversal permutation of $0,1,\ldots,N-1$.

For example, when $t=2$ ($N=4$) the bit‑reversed order of $0,1,2,3$ is $0,2,1,3$; placing $4,3,2,1$ in that order gives $K = (4,2,3,1)$. When $t=3$ ($N=8$) the order is $0,4,2,6,1,5,3,7$, yielding $K = (8,4,6,2,7,3,5,1)$.

Because the conditions at every level are simultaneously satisfiable and any violation strictly reduces the number of moves at some merge without increasing it elsewhere, this permutation is the unique maximiser of the total number of move operations in Algorithm D.

This completes the proof. ∎