# Why does decreasing the gap size in Shell sort never undo previous sorts?

I came across this sentence in the Wikipedia article on Shell short, which states that

If the file is then k-sorted for some smaller integer k, then the file remains h-sorted.

I've seen this claim in other texts like Lafore as well, but I can't wrap my head around why it's true. Of course I can't find a counterexample, but why must it be so?

• The best explanation (still hard to wrap the head around) is the description of shellsort by Knuth in "Sorting and Searching" Sep 12, 2015 at 10:21
• @vonbrand After looking in Knuth, I can follow the proof for Lemma L, but using it to prove Theorem K will require some more thought on my part. Ah, the good old "left as an exercise for the reader"... But really, thanks for mentioning this resource. Sep 12, 2015 at 12:38
• @MichaelH The solution to exercise 20 is given in the book. Sep 12, 2015 at 16:16

Here is an argument that I find a bit easier to understand than the ones I've seen online. It's not super rigorous, but I think it could be made so. To start with, the claim that you ask about can actually be made stronger and still be true. From Sedgewick and Wayne's Algorithms:

when an h-sorted array is k-sorted, it remains h-sorted

That is, we don't even need to assume that $k$ is less than $h$. Now, what does it mean that the array is $h$-sorted? Let us first define:

• An $h$-inversion of two elements $x_i$ and $x_j$, where $i < j$, is an inversion $inv(x_i,x_j)$ for which $j-i=h$.

Here, $i$ and $j$ are indices. Simply put, an $h$-inversion is an inversion between elements that are $h$ indices apart in the array. Then we can define:

• An $h$-sorted array is an array with no $h$-inversions.

If we accept these definitions, we only need to show that $k$-sorting the array does not increase the number of $h$-inversions. We will do so by looking at what might happen when we swap two elements $x_i$ and $x_{i+k}$ during a $k$-sort. But first, let's adopt the following notation:

• Let $x_i|$ and $x_{i+k}|$ denote the elements with index $i$ and $i+k$ before the swap, while $|x_i$ and $|x_{i+k}$ denotes the elements with index $i$ and $i+k$ after the swap.

Then, because we only swap the elements $x_i$ and $x_{i+k}$ if $x_i > x_{i+k}$, we have

• $|x_{i+k} = x_i| > x_{i+k}| = |x_i$.

The equalities are obvious because the left hand and right hand sides really refer to the same element, before and after the swap. The notable thing is the inequality, which we will be using soon.

To keep things easy to visualize, let us look at two elements that are to the right of both $x_i$ and $x_{i+k}$. More specifically, the elements $x_{i+h}$ and $x_{i+k+h}$, with $h>k$.

$$\left\{\ldots, x_i, \ldots, x_{i+k}, \ldots, x_{i+h}, \ldots, x_{i+k+h}, \ldots\right\}$$

Since the array starts out $h$-sorted, we have

• $x_i| < x_{i+h}$ , and
• $x_{i+k}| < x_{i+k+h}$.

After the swap we have,

• $|x_i < x_{i+h}$, because $|x_i < x_i|$, as established previously. Thus, no new inversion has been introduced involving indexes $i$ and $i+h$.

And for $x_{i+k}$ and $x_{i+k+h}$ we have either

• $|x_{i+k} < x_{i+k+h}$, in which case no new inversion is introduced involving indexes $i+k$ and $i+k+h$,

or, and this is key,

• $|x_{i+k} > x_{i+k+h}$, in which case a new $h$-inversion $inv(x_{i+k},x_{i+k+h})$ has been introduced. However, since $x_{i+k+h} < |x_{i+k} = x_i| < x_{i+h}$ and $x_{i+k+h}$ is $k$ positions to the right of $x_{i+h}$, we know that $x_{i+h}$ and $x_{i+k+h}$ will be swapped later in the $k$-sort, eliminating the $h$-inversion.

Thus, after the full $k$-sort, any such $h$-inversions introduced by the sort will have also been resolved by the sort.

We have only specifically looked at elements to the right of both $x_i$ and $x_{i+k}$, but very similar arguments can be made for elements to the left of both, or even with one element sitting in between (when $h<k$). I won't go into those cases here however, because this is already a long post.

Hint. Let $S$ be a $q$-tuple of some natural numbers, where $q$ is the length of list that we want to sort, and $\pi_k(S)$ denote the $k$-th element of $S$ (representing the $k$-th number in the list). Performing $g$-sorting on the list is equivalent to:

Creating the set $\mathcal{O}_g$

$$\mathcal{O}_g = \{ makeSet(n) : n \in \mathbb{N} : i < g \}$$

where $makeSet(n)$ is used to obtain all the natural numbers $k$ smaller than $q$ where $k$ modulo $g$ gives $n$.

$$makeSet(n) = \{ k : k \in \mathbb{N} : k \equiv n \pmod g \}$$

and then swapping the positions of the elements of $S$ based on every set in $\mathcal{O}_g$ such that the formula below is satisfied :

$$\forall A \in \mathcal{O}_g \; \forall a,b \in A \quad \pi_a(S) > \pi_b(S) \Leftrightarrow a >b$$

Now let's suppose we first perform $i$-sorting on some a list (represented as the $q$-tuple, $S$) and then perform $j$-sorting on the list again, where $i>j$:

$S$ would still satisfy the formula above for $\mathcal{O}_i$ is what the sentence in Wikipedia means.