We first sort all elements that are at distance

H.1 from each other, then re-sort the array using increment

H.2, finally we do an ordinary insertion sort with increment

1 (

H.1>H.2>...>1). D. L. Shell, the originator of the algorithm, took

H=N%2 as the first value of

H and used the formula

H=H%2. A sequence which has been shown empirically to do well is

H=...,1093,364,121,40,13,4,1

i.e H=(3**K-1)/2 which can be generated by the formula H=3*H+1 with the initial value H=1. The number of operations required in all is of order O(N**(3/2)) for the worst possible ordering of the original data. In average the operations count goes approximately as O(N**1.25).

The following table compares four sorting algorithms. The A. array includes integers in the range 1 to Max=10,100,1000,40000.