On one sort of commutative permutations

[mospehraict]

Abstract: We review one of the foundations of the Shell sort algorithm, namely h-sorting, and prove main point of the algorithm's correctness: that h-sorted array remains h-sorted after g-sorting it. This fact yields one type of commutative permutations.

Suppose a is an array of elements of a totally ordered set.

Let's define an array g-slices
ag1 = {a[0], a[g], a[2g], ..., a[kg], ...}
ag2 = {a[1], a[g+1], a[2g+1], ...}
...
agg-1 = {a[g-1], a[2g-1], ...},

where a[k] <- a.

Let's define an array is g-sorted if all of its g-slices are sorted,
that is a[i] <= a[i+g] for all i.

Now, suppose array a is h-sorted, that is, a[i] <= a[i+h], for all i.
Suppose P is a permutation, that sorts each of a's g-slice,
so that Pa is g-sorted, so P is a g-sorting permutation.

Proposition:
h-sorted array remains h-sorted after g-sorting it, that is,
Pa[i] <= Pa[i+h] for all i.


Proof:
without sacrificing generality, we put i=0.

Let's try prove that Pa is h-sorted by contradiction, that is,
suppose Pa[0] > Pa[h].

In general case:

Pa[0] = a[mg]
Pa[h] = a[h+ng]

a[mg] > a[h+ng]

By hypothesis,

a[ng] <= a[h+ng]

Pa[0] = a[mg] => (a[mg] must be smallest from all a[kg] for all k to go into Pa[0])
a[mg] <= a[ng] => (use hypothesis)
a[mg] <= a[h+ng]

Now we've got contradiction:
a[mg] > a[h+ng]
a[mg] <= a[h+ng]

QED.

For arbitrary i:

Let's try prove that Pa is h-sorted by contradiction, that is,
suppose Pa[i] > Pa[i+h], for some i.

In general case:

Pa[i] = a[i+mg]
Pa[i+h] = a[i+h+ng]

let's assume that m>=0, n>=0
(if it's not, then inverse the indexes. suppose Pa[i] = a[i+mg], and m<0, let's set
i+mg =: j
i = j-mg
Therefore, Pa[j] = a[j+ng], n = -m, n>0).

a[i+mg] > a[i+h+ng]

By hypothesis,

a[i+ng] <= a[i+h+ng]

Pa[i] = a[i+mg] => (a[i+mg] must be smallest from all a[i+kg] for all k to go into Pa[i])
a[i+mg] <= a[i+ng] => (use hypothesis)
a[i+mg] <= a[i+h+ng]

Now we've got contradiction:
a[i+mg] > a[i+h+ng]
a[i+mg] <= a[i+h+ng]

QED.

Corollary 1. Let Ph and Pg be h- and g-slice sorting permutations, then they are commutative.
Proof.

By main theorem if Pha = a, then PgPha = Pga = PhPga, QED.

Corollary 2. If array is h-sorted and g-sorted, then it's also (h+g)-sorted.
Proof.

By main theorem, if a is h-sorted and g-sorted, then
a[i] <= a[i+h] <= a[i+h+g]
QED.