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 < 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.

• What do you mean by "remains h-sorted"? What is the remains? You haven't said anything about any changes to the list. Are you changing the list? Please edit the question to make it self-contained, so we don't have to click some external link to understand what you are asking. – D.W. Sep 19 '17 at 15:57
• @D.W. I quoted the entire paragraph from Wikipedia which contains the sentence. Is it okay now? – user77250 Sep 19 '17 at 16:08
• I agree. This question only makes sense looking at (a specific form of?) Shellsort. (By the way, you may want to get a textbook. The average quality of algorithms articles on Wikipedia is dreadful.) – Raphael Sep 19 '17 at 16:18
• @Raphael It's applicable for any shell-sort. (Say) In the first step if a list is 6-sorted, then the sentence claims that even if you 5-sort, or 4-sort,or ...., or 1-sort it; the list remains 6-sorted. – user77250 Sep 19 '17 at 16:27
• It's surprisingly hard to find a proof you're looking for. Knuth has a pretty clear one in TAOCP, v.3. [If you don't know what that is, look it up; it should be a reference on the shelves of every computer scientist.] – Rick Decker Sep 20 '17 at 0:27

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] < 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".