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?

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

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+k}|

After the swap we have,

• $|x_i

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

• $|x_{i+k}

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}

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.

StackExchange Computer Science Q#47096, answer score: 5