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 < 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 < 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 < x_k$. So the last entry in the final $m$-sorted array $B$ is $x_k$. Sum it up: $x_m < x_0 < x_n < 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 < 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} < x_n$. And then on the last entry, $x_k$ (in the $2n-m$ th position) and $x_{2n}$ are switched. Then $x_{2n} < 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 < x_m < x_{n+m} < x_n < x_{2n} < x_k$, where $x_m < 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.
