Shellsort

thumb|alt=The steps of Shellsort.|Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be understood as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort).

Description

Shellsort is an optimization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, taking every hth element produces a sorted list. Such a list is said to be h-sorted. It can also be thought of as h interleaved lists, each individually sorted. Beginning with large values of h allows elements to move long distances in the original list, reducing large amounts of disorder quickly, and leaving less work for smaller h-sort steps to do. If the list is then k-sorted for some smaller integer k, then the list remains h-sorted. A final sort with h = 1 ensures the list is fully sorted at the end,

|----

|

| <math>2^k - 1</math>

| <math>1, 3, 7, 15, 31, 63, \ldots</math>

| <math>\Theta\left(N^\frac{3}{2}\right)</math>

| Hibbard, 1963

|----

|

| <math>2^k + 1</math>, prefixed with 1

| <math>1, 3, 5, 9, 17, 33, 65, \ldots</math>

| <math>\Theta\left(N^\frac{3}{2}\right)</math>

| Papernov & Stasevich, 1965

|----

|

| Successive numbers of the form <math>2^p 3^q</math> (3-smooth numbers)

| <math>1, 2, 3, 4, 6, 8, 9, 12, \ldots</math>

| <math>\Theta\left(N \log^2 N\right)</math>

| Pratt, 1971 based on Pratt, 1971 Knuth

|----

|

| <math>h_k = \max\left\{\left\lfloor \frac{5h_{k-1}-1}{11} \right\rfloor, 1\right\}, h_0 = N</math>

| <math>1, \ldots, \left\lfloor \frac{5}{11}\left\lfloor \frac{5N-1}{11} \right\rfloor-\frac{1}{11}\right\rfloor,

\left\lfloor \frac{5N-1}{11} \right\rfloor

</math>

| <math>\Theta\left(N^2\right)</math> [for certain values of N]

| Gonnet & Ricardo Baeza-Yates|, 1991

|----

|

| <math>\left\lceil \frac{1}{5} \left(9\cdot \left(\frac{9}{4}\right)^{k-1} - 4 \right) \right\rceil</math> (or equivalently, <math>\left\lceil \frac{\left(9/4\right)^k-1}{\left(9/4\right)-1} \right\rceil</math>)

| <math>1, 4, 9, 20, 46, 103, \ldots</math>

|

| Tokuda, 1992 (misquote per OEIS)

|----

|

| Unknown (experimentally derived)

| <math>1, 4, 10, 23, 57, 132, 301, 701</math><!--Please don't add 1750. It doesn't belong here.-->

|

| Ciura, 2001

|----

|

| <math>\left\lceil \frac{\gamma^k-1}{\gamma-1} \right\rceil, \gamma = 2.243609061420001\ldots</math>

| <math>1, 4, 9, 20, 45, 102, 230, 516, \ldots</math>

|

| Lee, 2021

|----

|

| <math>\left\lfloor 4.0816\cdot 8.5714^{\frac{k}{2.2449 \right\rfloor</math>

| <math>1, 4, 10, 27, 72, 187, 488, \ldots</math>

|

| Skean, Ehrenborg, Jaromczyk, 2023

|}

When the binary representation of N contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(N²) 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.

The Gonnet and Baeza-Yates implementation of Shellsort (GBY91) also uses gaps that start with N and performs better than many of the other sequences on average

With respect to the average number of comparisons, Ciura's sequence For N = 128 and N = 1000, Ciura empirically found that (1, 4, 9, 24, 85) and (1, 4, 10, 23, 57, 156, 409, 995) made the fewest number of comparisons on average respectively. Every h₁-sorted and h₂-sorted array is also (a₁h₁+a₂h₂)-sorted, for any nonnegative integers a₁ and a₂. The worst-case complexity of Shellsort is therefore connected with the Frobenius problem: for given integers h₁,..., h_n with gcd = 1, the Frobenius number g(h₁,..., h_n) is the greatest integer that cannot be represented as a₁h₁+ ... +a_nh_n with nonnegative integer a₁,..., a_n. Using known formulae for Frobenius numbers, we can determine the worst-case complexity of Shellsort for several classes of gap sequences. Proven results are shown in the above table.

Mark Allen Weiss proved that Shellsort runs in O(N log N) time when the input array is in reverse order.

With respect to the average number of operations, none of the proven results concerns a practical gap sequence. For gaps that are powers of two, Espelid computed this average as <math>0.5349N\sqrt{N}-0.4387N-0.097\sqrt{N}+O(1)</math>. Knuth determined the average complexity of sorting an N-element array with two gaps (h, 1) to be <math>\frac{2N^2}{h} + \sqrt{\pi N^3 h}</math>. His result was refined by Janson and Knuth: the average number of comparisons/inversions/running time made during a Shellsort with three gaps (ch, cg, 1), where h and g are coprime, is <math>\frac{N^2}{4ch} + O(N)</math> in the first pass, <math>\frac{1}{8g}\sqrt{\frac{\pi}{ch(h - 1)N^{3/2} + O(hN)</math> in the second pass and <math>\psi(h, g)N + \frac{1}{8}\sqrt{\frac{\pi}{c(c - 1)N^{3/2} + O\left((c - 1)gh^{1/2}N\right) + O\left(c^2g^3h^2\right)</math> in the third pass. ψ(h, g) in the last formula is a complicated function asymptotically equal to <math>\sqrt{\frac{\pi h}{128g + O\left(g^{-1/2}h^{1/2}\right) + O\left(gh^{-1/2}\right)</math>. In particular, when h = Θ(N^7/15) and g = Θ(N^1/5), the average time of sorting is O(N^23/15).

Based on experiments, it is conjectured that Shellsort with Hibbard's gap sequence runs in O(N^5/4) average time, proved the following lower bound for the order of the average number of operations/running time in a p-pass Shellsort: Ω(pN^1+1/p) when p&nbsp;≤&nbsp;log₂N and Ω(pN) when p&nbsp;>&nbsp;log₂N.

Therefore, Shellsort has prospects of running in an average time that asymptotically grows like N logN only when using gap sequences whose number of gaps grows in proportion to the logarithm of the array size. It is, however, unknown whether Shellsort can reach this asymptotic order of average-case complexity, which is optimal for comparison sorts. The lower bound was improved by Vitányi for every number of passes <math>p</math> to

<math>

\Omega ( N\sum_{k=1}^p h_{k-1}/h_k )

</math>

where <math>h_0=N</math>. This result implies for example the Jiang-Li-Vitányi lower bound for all <math>p</math>-pass increment sequences and improves that lower bound for particular increment sequences. In fact all bounds (lower and upper) currently known for the average case are precisely matched by this lower bound. For example, this gives the new result that the Janson-Knuth upper bound is matched by the resulting lower bound for the used increment sequence, showing that three pass Shellsort for this increment sequence uses <math>\Theta(N^{23/15})</math> comparisons/inversions/running time.

The formula allows us to search for increment sequences that yield lower bounds which are unknown; for example an increment sequence for four passes which has a lower bound greater than

<math>\Omega(pn^{1+1/p}) = \Omega(n^{5/4})</math> for the increment sequence

<math>h_1 = n^{11/16},</math> <math>h_2 = n^{7/16},</math> <math>h_3 = n^{3/16},</math> <math>h_4 = 1</math>. The lower bound becomes

<math>T = \Omega(n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3/16}) = \Omega(n^{1+5/16}) = \Omega(n^{21/16}).</math>

The worst-case complexity of any version of Shellsort is of higher order: Plaxton, Poonen, and Suel showed that it grows at least as rapidly as <math>\Omega\left(N \left( {\log N \over \log \log N} \right)^2\right)</math>.

Robert Cypher proved a stronger lower bound: <math>\Omega\left(N \right)</math> when <math>h_{s+1} > h_s</math> for all <math>s</math>.

Applications

Shellsort performs more operations and has higher cache miss ratio than quicksort. However, since it can be implemented using little code and does not use the call stack, some implementations of the qsort function in the C standard library targeted at embedded systems use it instead of quicksort. Shellsort is, for example, used in the uClibc library. For similar reasons, in the past, Shellsort was used in the Linux kernel.

Shellsort can also serve as a sub-algorithm of introspective sort, to sort short subarrays and to prevent a slowdown when the recursion depth exceeds a given limit. This principle is employed, for instance, in the bzip2 compressor.

See also

• Comb sort

References

Bibliography

• Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.

External links

• – graphical demonstration
• Shellsort with gaps 5, 3, 1 as a Hungarian folk dance