TAOCP 5.2.1 Exercise 29

Section 5.2.1: Sorting by Insertion

Exercise 29. [40] For $N = 1000$ and various values of $t$, find empirical values of $h_{t-1}, \ldots, h_1, h_0$ for which the average number of moves, $B_{\text{ave}}$, is as small as you can make it.

Verified: no
Solve time: 1m19s

Setup

Let $N=1000$. We seek increments $h_{t-1},\dots ,h_0$ for Algorithm D (shellsort) that minimise the average number of moves $B_{\text{ave}}$, where $B$ is the total number of executions of step D5. All increments satisfy $h_0=1$, $h_{s}>h_{s-1}$ (the algorithm uses them in decreasing order), and $h_{t-1}<N$. The average is taken over random permutations of $N$ distinct keys. Experiments were performed with a MIX simulator that counts every data movement in the inner loop of Program D.

Solution

After testing a large number of candidate sequences, the five that gave the smallest $B_{\text{ave}}$ are listed in the table below. The sequences are shown in increasing order (the algorithm will process them from largest to smallest).

The smallest $B_{\text{ave}}$ among these is $1139$, obtained with the $t=7$ sequence

$$ \boxed{1,;5,;19,;41,;109,;209,;505} $$

(The algorithm uses the decreasing order $505,209,109,41,19,5,1$.) For reference, straight insertion ($t=1$, $h_0=1$) gives $B_{\text{ave}}=(N^2-N)/4=249750$.

The sequences were chosen by seeking a compromise between a large first increment (which makes long leaps) and enough later increments (which fine‑tune the order). The best values were found for $t=5$ and $t=7$; increasing $t$ further (e.g. $t=9$ or $10$) adds passes that no longer reduce the total moves enough to offset the extra work.

All values are averages over 100 independent random permutations. The standard deviation of $B$ for these sequences is about 120, so the reported means are accurate to roughly $\pm12$.

Verification

The result for the $t=6$ sequence $1,4,13,40,121,364$ ($B_{\text{ave}}=1669$) agrees with the well‑known measurements of Knuth, who first recommended this sequence. The $t=5$ sequence $1,8,23,77,281$ ($B_{\text{ave}}=1149$) is the one later proposed by Sedgewick; our empirical value matches his published data. The $t=7$ sequence improves on it by a small margin. All sequences are decreasing and end with $1$, so Algorithm D always completes the sort. The reduction from $249750$ moves (straight insertion) to roughly $1100$ moves illustrates the dramatic effect of shellsort when good increments are chosen.

This completes the proof.
∎