Shellsort - Gap Sequences

Gap Sequences

Every gap sequence that contains 1 yields a correct sort; however, the properties of thus obtained versions of Shellsort may be very different.

The table below compares most proposed gap sequences published so far. Some of them have decreasing elements that depend on the size of the sorted array (N). Others are increasing infinite sequences, whose elements less than N should be used in reverse order.

General term (k ≥ 1)	Concrete gaps	Worst-case time complexity	Author and year of publication
	$\left\lfloor\frac{N}{2}\right\rfloor, \left\lfloor\frac{N}{4}\right\rfloor, \ldots, 1$		Shell, 1959
			Frank & Lazarus, 1960
			Hibbard, 1963
, with 1 prepended			Papernov & Stasevich, 1965
successive numbers of the form			Pratt, 1971
, not greater than			Knuth, 1973
$\prod \limits_{\scriptscriptstyle 0\le q<r\atop \scriptscriptstyle q\neq(r^2+r)/2-k}a_q, \hbox{where}$			Incerpi & Sedgewick, 1985
, with 1 prepended			Sedgewick, 1986
			Sedgewick, 1986
		?	Gonnet & Baeza-Yates, 1991
		?	Tokuda, 1992
unknown		?	Ciura, 2001

When the binary representation of N contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(N2) comparisons in the worst case. For instance, this case occurs for N equal to a power of two when elements greater and smaller than the median occupy odd and even positions respectively, since they are compared only in the last pass.

Although it has higher complexity than the O(NlogN) that is optimal for comparison sorts, Pratt's version lends itself to sorting networks and has the same asymptotic gate complexity as Batcher's bitonic sorter.

Gonnet and Baeza-Yates observed that Shellsort makes the fewest comparisons on average when the ratios of successive gaps are roughly equal to 2.2. This is why their sequence with ratio 2.2 and Tokuda's sequence with ratio 2.25 prove efficient. However, it is not known why this is so. Sedgewick recommends to use gaps that have low greatest common divisors or are pairwise coprime.

With respect to the average number of comparisons, the best known gap sequences are 1, 4, 10, 23, 57, 132, 301, 701 and similar, with gaps found experimentally. Optimal gaps beyond 701 remain unknown, but good results can be obtained by extending the above sequence according to the recursive formula .

Tokuda's sequence, defined by the simple formula, where, can be recommended for practical applications.

Famous quotes containing the word gap:

“Here is the place; right over the hill
Runs the path I took;
You can see the gap in the old wall still,
And the stepping-stones in the shallow brook.”
—John Greenleaf Whittier (1807–1892)