TAOCP 5.2.1 Exercise 30
Let the set of increments be \[ S = \{\,2^{p}3^{q}\mid 2^{p}3^{q}<N,\;p,q\ge 0\,\}.
Section 5.2.1: Sorting by Insertion
Exercise 30. [M23] (N. Pratt.) If the set of increments in shellsort is ${2^p 3^q \mid 2^p 3^q < N}$, show that the number of passes is approximately $\frac{1}{2}(\log_2 N)(\log_3 N)$, and the number of moves per pass is at most $N/2$. In fact, if $K_{j-h} > K_j$ on any pass, we will always have $K_{j-h} - K_{j-2h} \le K_j - K_{j-h} \le K_{j+h} - K_j$; so we may simply interchange $K_{j-h}$ and $K_j$ and increase $j$ by $2h$, saving two of the comparisons of Algorithm D. Hint: See exercise 25.
Verified: no
Solve time: 2m42s
Solution
Number of passes
Let the set of increments be
[ S = {,2^{p}3^{q}\mid 2^{p}3^{q}<N,;p,q\ge 0,}. ]
The number of passes is (|S|). For each fixed (p), the admissible (q) satisfy
(3^{q}<N/2^{p}); hence the number of such (q) is
[ q_{\max}(p)+1,\qquad q_{\max}(p)=\bigl\lfloor\log_{3}(N/2^{p})\bigr\rfloor, ]
provided (2^{p}<N). Summing over (p),
[ |S|=\sum_{p=0}^{\lfloor\log_{2}(N-1)\rfloor}\bigl(\lfloor\log_{3}(N/2^{p})\rfloor+1\bigr). ]
Approximating the sum by an integral,
[ \begin{aligned} |S|&\approx\int_{0}^{\log_{2}N}\Bigl(\log_{3}(N/2^{x})+1\Bigr),dx\ &=\int_{0}^{\log_{2}N}\bigl(\log_{3}N-x\log_{3}2+1\bigr),dx\ &=(\log_{3}N+1)\log_{2}N-\frac12(\log_{2}N)^{2}\log_{3}2\ &=\frac12\frac{(\log N)^{2}}{\log2\log3}+O(\log N). \end{aligned} ]
Since (\log_{2}N=\log N/\log2) and (\log_{3}N=\log N/\log3), the dominant term is
[ \frac12\bigl(\log_{2}N\bigr)\bigl(\log_{3}N\bigr). ]
Thus the number of passes is approximately (\displaystyle\frac12(\log_{2}N)(\log_{3}N)).
Moves per pass
Let (h) be any increment that belongs to (S). Before the (h)-sort we have sorted with all larger increments; in particular, if (2h<N) then (2h) is also an increment (because (2h = 2^{p+1}3^{q}) when (h=2^{p}3^{q})), so the array is (2h)-sorted:
[ K_{i}\le K_{i+2h}\qquad\text{for all }i\le N-2h. \tag{1} ]
If (2h\ge N) the bound is trivial (see below).
Consider the (h)-subsequences: for each residue (r;(1\le r\le h)) the positions (r,;r+h,;r+2h,;\dots) form a sequence of length (m_{r}). Because of (1), within such a subsequence we have
[ K_{r+kh}\le K_{r+(k+2)h}\qquad\text{for all }k. \tag{2} ]
Now examine consecutive pairs in the subsequence. If an inversion occurs at step (k), i.e.
[ K_{r+kh}>K_{r+(k+1)h}, ]
then (2) gives
[ K_{r+(k+1)h}<K_{r+kh}\le K_{r+(k+2)h}, ]
so (K_{r+(k+1)h}<K_{r+(k+2)h}). Hence the very next pair, ((r+(k+1)h,;r+(k+2)h)), is not inverted. Therefore inversions cannot occur at two consecutive positions in the same (h)-subsequence.
A subsequence of length (m_{r}) contains (m_{r}-1) consecutive pairs; at most (\lceil(m_{r}-1)/2\rceil) of them can be inversions. Since (\lceil(m_{r}-1)/2\rceil\le m_{r}/2) for every (m_{r}\ge1), the total number of inversions over all residues is
[ \sum_{r=1}^{h}\bigl(\text{inversions in subsequence }r\bigr) ;\le;\sum_{r=1}^{h}\frac{m_{r}}{2} ;=;\frac12\sum_{r=1}^{h}m_{r} ;=;\frac{N}{2}. ]
For the case (2h\ge N): every (h)-subsequence has at most two elements. A subsequence of length 2 contributes at most one inversion; a subsequence of length 1 contributes none. The number of residues that contain two elements is (N-h); hence the total number of inversions is at most (N-h). Because (2h\ge N) implies (h\ge N/2), we have (N-h\le N/2). Thus the bound (\le N/2) holds for all (h).
When we execute the (h)-sort, each inverted pair (\bigl(K_{i},K_{i+h}\bigr)) can be corrected by a single interchange of the two keys. The property that inversions are never consecutive guarantees that after swapping, the neighbouring pairs are already in order; consequently each inversion is fixed exactly once and no element is moved more than once in this interchange process. Hence the number of record moves (interchanges) performed during the (h)-sort equals the number of inversions, which we have shown is at most (N/2).
Therefore, for every increment in ({,2^{p}3^{q}<N,}), the number of moves per pass is at most (N/2).
This completes the proof. ∎