Shellsort

Algorithm: Move entries more than one position at a time by h-sorting the array. How to h-sort an array? Insertion sort, with stride length h.

Proposition. A g-sorted array remains g-sorted after h-sorting it.

Complexity: Proposition. The worst-case number of compares used by shellsort with the 3x+1 increments is $\mathcal{O}(N^{3/2})$. Property. Number of compares used by shellsort with the 3x+1 increments is at most by a small multiple of N times the # of increments used.