DescriptionShellsort, also known as Shell sort or Shell's method is an in-place comparison sort. It generalizes an exchanging sort, such as insertion or bubble sort, by allowing the comparison and exchange of elements that lie far apart. Its first version was published by Donald Shell in 1959. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.It is a multi-pass algorithm. Each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment). This is referred to as h-sorting. It is an unstable: it may change the relative order of elements with equal values. It has "natural" behavior, in that it executes faster when the input is partially sorted.
Gap sequencesEvery 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 |
|Author and year of publication|
|Θ(N2) [when N=2p]||Shell, 1959|
|Θ(N3 / 2)||Frank & Lazarus, 1960|
|2k − 1||Θ(N3 / 2)||Hibbard, 1963|
|2k + 1, with 1 prepended||Θ(N3 / 2)||Papernov & Stasevich, 1965|
|successive numbers of the form 2p3q||Θ(Nlog 2N)||Pratt, 1971|
|(3k − 1) / 2, not greater than||Θ(N3 / 2)||Knuth, 1973|
|Incerpi & Sedgewick, 1985|
|, with 1 prepended||O(N4 / 3)||Sedgewick, 1986|
|O(N4 / 3)||Sedgewick, 1986|
|?||Gonnet & Baeza-Yates, 1991|
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 h'k = 2.25h'k − 1 + 1, h'1 = 1, can be recommended for practical applications.