Why does decreasing the gap size in Shell sort never undo previous sorts?
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 &lt; 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 &gt; x_{i+k}$, we have


$ |x_{i+k} = x_i| &gt; 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&gt;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| &lt; x_{i+h}$ , and
$x_{i+k}| &lt; x_{i+k+h}$.


After the swap we have,


$|x_i &lt; x_{i+h}$, because $|x_i &lt; 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} &lt; 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} &gt; 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} &lt; |x_{i+k} = x_i| &lt; 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&lt;k$). I won't go into those cases here however, because this is already a long post.