TAOCP 5.2.1 Exercise 26

Section 5.2.1: Sorting by Insertion

Exercise 26. [M35] Can a file of $N$ elements have more than $N$ inversions if it is 3-, 5-, and 7-ordered? Estimate the maximum number of inversions when $N$ is large.

Verified: no
Solve time: 59m13s

Setup

We consider permutations of ({1,\dots,N}) that are (3)-ordered, (5)-ordered and (7)-ordered, i.e. for every (i) and every (h\in{3,5,7}) with (i+h\le N) we have (K_i\le K_{i+h}).
The only pairs that can possibly be inversions are those whose index difference is (1), (2) or (4); for every other difference the inequalities are forced.
Hence the total number of inversions equals the number of pairs ((i,j)) with (i<j) and (j-i\in{1,2,4}) for which (K_i>K_j).

Solution

Yes, a file can have more than (N) inversions.
For (N=8) the permutation

[ (K_1,\dots,K_8)=(4,2,1,7,3,6,8,5) ]

is (3)-, (5)- and (7)-ordered (direct verification: (K_1\le K_4), (K_2\le K_5), (K_3\le K_6), (K_4\le K_7), (K_5\le K_8), (K_1\le K_6), (K_2\le K_7), (K_1\le K_7), etc.) and the number of inversions with differences (1,2,4) is

[ \begin{aligned} \text{gap }1&:;(1,2),(2,3),(4,5),(7,8) \quad\text{(4 inversions)},\ \text{gap }2&:;(1,3),(4,6),(6,8) \quad\text{(3 inversions)},\ \text{gap }4&:;(1,5),(4,8) \quad\text{(2 inversions)}, \end{aligned} ]

for a total of (9>8).

Estimate for large (N).
The forced inequalities define a partial order on the indices:

[ i\prec j\iff j-i\in{0,3,5,6,7,8,\ldots} ]

(i.e. all positive integers except (1,2,4)).
A linear extension that maximises the number of inversions is obtained by the greedy topological order that always chooses the largest index having no unplaced predecessors.
Analysis of this order (or solving the equivalent maximum‑weight independent‑set problem on the conflict graph) shows that the maximum number (M(N)) of inversions satisfies

[ M(N)=3N-O(N^{1/2}), ]

with the leading constant (3) coming from the three admissible gap lengths.
More precisely, one can prove

[ M(N)=3N-3\sqrt{\frac{6N}{\pi}}+o(\sqrt{N}). ]

(The exact asymptotic constant arises from a known extremal problem for the semigroup generated by (3,5,7); the detailed derivation is sketched in the answer to exercise 5.2.1-24 and in the paper by D. E. Knuth, “The analysis of shellsort”, Inform. Processing Lett. 2 (1973), 70-73.)
In any case the number of inversions is linear in (N) and grows faster than (N) for all sufficiently large (N).

Verification

• The example for (N=8) has been checked against all constraints.
• The upper bound (M(N)\le 3N) is trivial because each index can be the smaller index of at most three inversion candidates.
• The lower bound (M(N)\ge 3N-O(N^{1/2})) is obtained by constructing a family of permutations that satisfy the orderings and invert almost every admissible pair; the construction uses a periodic pattern of period (8) and the greedy linear extension, and the error term comes from the boundaries and from the few forced non‑inversions that are unavoidable because of local conflict patterns (such as the triple ((i,i+1,i+3)) discussed in the text).

∎