Proof: "If the list is then k-sorted for some smaller integer k, then the list remains h-sorted" Shellsort is a generalization of insertion sort that allows the
  exchange of items that are far apart. The idea is to arrange the list
  of elements so that, starting anywhere, considering every hth element
  gives a sorted list. Such a list is said to be h-sorted. Equivalently,
  it can be thought of as h interleaved lists, each individually
  sorted. Beginning with large values of h, this rearrangement allows
  elements to move long distances in the original list, reducing large
  amounts of disorder quickly, and leaving less work for smaller h-sort
  steps to do. If the list is then k-sorted for some smaller integer
  k, then the list remains h-sorted. Following this idea for a
  decreasing sequence of h values ending in 1 is guaranteed to leave a
  sorted list in the end.


[Source]

What is the mathematical proof for the quoted claim (in bold)?

An attempt at the proof (for the case when number of elements is $2n+1$):



My initial array is $A = \{x_0, \cdots, x_n\}$ and i have $x_0 &lt; x_n$. Say that after first pass $x_0$ switches place with $x_m$, so the final array $B$ starts with the entry $x_m$ regardless of the position of $x_0$ (which can further switch place with $x_{2m}$ and so on). Thus, $x_m &lt; x_0$. Now, in the final pass $x_n$ can switch place with $x_k$ (which, before the last pass, is in the $(n-m)$-th position in the array). We don't care about $k$, but we just know that $x_n &lt; x_k$. So the last entry in the final $m$-sorted array $B$ is $x_k$.
Sum it up: $x_m &lt; x_0 &lt; x_n &lt; x_k$.

That means $B$ is $n$-sorted.
If we assumed the switchings of $x_0$ and $x_n$ didn't happen during $m$-sorting, we are trivially done, because the starting and final entries of $B$ are $x_0$ and $x_n$ respectively, and since $x_0 &lt; x_n$, $B$ is $n$-sorted.

Say $A = \{x_0, \cdots, x_n, \cdots, x_{2n}\}$ is $n$-sorted. We can assume the subarray $\{x_0, \cdots, x_n\}$ is $m$-sorted WLOG and because of what we proved earlier. Suppose now that while $m$-sorting, $x_n$ and $x_{n+m}$ are switched; then $x_{n+m} &lt; x_n$. And then on the last entry, $x_k$ (in the $2n-m$ th position) and $x_{2n}$ are switched. Then $x_{2n} &lt; x_k$.

After the $m$-sorting is over, the $n$-gap subarray starting at $x_0$ is $\{x_0, x_{n+m}, x_k\}$. We have $x_0 &lt; x_m &lt; x_{n+m} &lt; x_n &lt; x_{2n} &lt; x_k$, where $x_m &lt; x_{n+m}$ is because $A$ is $n$-sorted.

So, this is proof that if a $2n+1$ array is $m$-sorted after being $n$-sorted, it remains $n$ sorted.



However, I don't know how to generalize that for any size of array.
the claim follows easily from a careful definition of "k-sorted". define k-sorted as "for all i there does not exist a j > k such that for two elements in the list a[i+j] &lt; a[i]." then if a list is k-sorted, it is h-sorted for h > k.  

to look into deeper/ more general theory realize that k-sorted is a "measure of disorder" eg as in question how to measure sortedness. see this paper a survey of adaptive sorting algorithms, / Castro, Wood, measures of disorder, sec 1.2. h-sorted appears to be equivalent to measure #1, Dis, "largest distance determined by an inversion".