TAOCP 5.2.1 Exercise 16
Let $n$ and $h$ be positive integers.
Section 5.2.1: Sorting by Insertion
Exercise 16. [M2] Find a formula for the maximum number of inversions in an $h$-ordered permutation of ${1, 2, \ldots, n}$. What is the maximum possible number of moves in Algorithm D when the increments satisfy the divisibility condition (5)?
Verified: no
Solve time: 53m18s
16.
Let $n$ and $h$ be positive integers.
Write $n = qh + r$ with $0 \le r < h$.
The $h$‑subsequences have lengths
[ L_j = \begin{cases} q+1, & 1\le j\le r,\[2pt] q, & r<j\le h . \end{cases} ]
1. Maximum inversions in an $h$‑ordered permutation
An $h$‑ordered permutation is obtained by placing numbers $1,\dots,n$ into a matrix with $h$ columns (the residue classes) and rows indexed by $k=0,1,\dots$, where column $j$ contains $L_j$ rows.
The permutation is the row‑major reading of the matrix, and the condition “$h$‑ordered” requires that each column be increasing downwards.
To maximise the number of inversions we assign the largest $L_1$ numbers to column 1, the next largest $L_2$ to column 2, …, the smallest $L_h$ to column $h$, and within each column we place the numbers in increasing order.
Then every number in column $i$ is larger than every number in column $j$ whenever $i<j$.
For such an assignment an inversion occurs precisely when two cells $(k_1,i)$ and $(k_2,j)$ satisfy $i<j$ and the cell from column $i$ comes before the cell from column $j$ in row‑major order.
Because positions are $k h + j$, the condition $k_1h+i < k_2h+j$ is equivalent to $k_1\le k_2$ (since $j-i<h$).
Hence for a fixed pair $i<j$ the number of inversion‑contributing pairs is
[ f(L_i,L_j)=\sum_{k=0}^{\min(L_i,L_j)-1}(L_j-k) = \begin{cases} L_iL_j-\displaystyle\binom{L_i}{2}, & L_i\le L_j,\[6pt] \displaystyle\binom{L_j+1}{2}, & L_i>L_j . \end{cases} ]
The total number of inversions is therefore
[ I_{\max}(n,h)=\sum_{1\le i<j\le h} f(L_i,L_j). ]
Substituting the lengths $L_j$ and simplifying gives
[ I_{\max}(n,h)=\frac14\Bigl(r(r-1)(q+1)(q+2)+q(q+1)(h-r)(h+r-1)\Bigr). ]
This is the maximum number of inversions that an $h$‑ordered permutation of ${1,\dots,n}$ can have.
(Any other assignment would either lose some of the pairs counted above or violate the column‑monotonicity; the construction shows the bound is attainable.)
2. Maximum number of moves in Algorithm D under the divisibility condition
Let the increments be $g_1>g_2>\dots>g_t=1$ with $g_{i-1}$ a multiple of $g_i$ for $2\le i\le t$.
Algorithm D processes them in the order $g_1,g_2,\dots,g_t$.
After the pass with $g_{i-1}$ the file is $g_{i-1}$‑ordered, and the divisibility condition guarantees that sorting with a divisor preserves the ordering of all multiples.
Hence before the pass with $g_i$ ($i\ge2$) the permutation is $g_{i-1}$‑ordered.
In a pass with increment $g$ the number of moves equals the total number of inversions inside the $g$-subsequences of the current permutation.
First pass ($g_1$): no prior constraint; a $g_1$-subsequence can be arranged arbitrarily, so the maximum number of inversions inside it is $\binom{L}{2}$, where $L$ is its length.
Thus the contribution of the first pass is
[ M_1=\sum_{j=1}^{g_1}\binom{L_{1,j}}{2},\qquad L_{1,j}= \Bigl\lfloor\frac{n-j}{g_1}\Bigr\rfloor+1 . ]
Pass $i;(2\le i\le t)$: at this stage the file is $g_{i-1}$‑ordered.
Let $m_i=g_{i-1}/g_i$ (an integer $\ge2$).
Each $g_i$-subsequence consists of $m_i$ residue classes modulo $g_{i-1}$, all of which are sorted.
The positions inside this $g_i$-subsequence are exactly those of an $m_i$-ordered permutation of its $L$ elements, with column lengths equal to the lengths of the constituent residue classes.
By the result of part 1 the maximum number of inversions that can appear inside such a subsequence is $I_{\max}(L,m_i)$.
Summing over all $g_i$-subsequences yields the contribution
[ M_i=\sum_{j=1}^{g_i} I_{\max}!\bigl(L_{i,j},,m_i\bigr),\qquad L_{i,j}= \Bigl\lfloor\frac{n-j}{g_i}\Bigr\rfloor+1 . ]
The function $I_{\max}$ is the one derived above (with $h=m_i$).
Because the contributions are independent and the constructive assignment used in part 1 can be applied recursively to achieve the maximum at every level simultaneously, the total maximum number of moves in Algorithm D under the divisibility condition is
[ \boxed{\displaystyle\sum_{i=1}^{t} M_i = \sum_{i=1}^{t};\sum_{j=1}^{g_i}; \Phi!\left(L_{i,j},,\frac{g_{i-1}}{g_i}\right)}, ]
where we set $g_0=n$, $g_t=1$, and
[ \Phi(L,m)= \begin{cases} \displaystyle\binom{L}{2}, & m=1,\[6pt] I_{\max}(L,m), & m\ge2 . \end{cases} ]
This completes the proof. ∎