Editing Shellsort (section)

== Computational complexity ==
The following property holds: after ''h''<sub>2</sub>-sorting of any ''h''<sub>1</sub>-sorted array, the array remains ''h''<sub>1</sub>-sorted.<ref>{{Cite journal
  |last1=Gale
  |first1=David
  |author-link=David Gale
  |last2=Karp
  |first2=Richard M.
  |author2-link=Richard M. Karp
  |title=A Phenomenon in the Theory of Sorting
  |journal=Journal of Computer and System Sciences
  |volume=6
  |issue=2
  |date=April 1972
  |pages=103–115
  |doi=10.1016/S0022-0000(72)80016-3
  |url=https://core.ac.uk/download/pdf/82277625.pdf
|doi-access=free
  }}</ref> Every ''h''<sub>1</sub>-sorted and ''h''<sub>2</sub>-sorted array is also (''a''<sub>1</sub>''h''<sub>1</sub>+''a''<sub>2</sub>''h''<sub>2</sub>)-sorted, for any nonnegative integers ''a''<sub>1</sub> and ''a''<sub>2</sub>. The worst-case complexity of Shellsort is therefore connected with the [[coin problem|Frobenius problem]]: for given integers ''h''<sub>1</sub>,..., ''h<sub>n</sub>'' with gcd = 1, the Frobenius number ''g''(''h''<sub>1</sub>,..., ''h<sub>n</sub>'') is the greatest integer that cannot be represented as ''a''<sub>1</sub>''h''<sub>1</sub>+ ... +''a<sub>n</sub>h<sub>n</sub>'' with nonnegative integer ''a''<sub>1</sub>,..., ''a<sub>n</sub>''. Using known formulae for Frobenius numbers, we can determine the worst-case complexity of Shellsort for several classes of gap sequences.<ref>{{Cite journal
  |last=Selmer
  |first=Ernst S.
  |author-link=Ernst Sejersted Selmer
  |title=On Shellsort and the Frobenius Problem
  |journal=BIT Numerical Mathematics
  |volume=29
  |issue=1
  |date=March 1989
  |pages=37–40
  |doi=10.1007/BF01932703
  |hdl=1956/19572
  |s2cid=32467267
 |hdl-access=free
  |url=https://bora.uib.no/bora-xmlui/bitstream/handle/1956/19572/On%20Shellsort%20and%20the%20Frobenius%20problem.pdf
}}</ref> 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.<ref>{{Cite journal
  |last=Weiss
  |first=Mark Allen
  |title=A good case for Shellsort
  |journal=Congressus Numerantium
  |volume=73
  |date=1989
  |pages=59–62
}}</ref>

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>.<ref>{{Cite journal
  |last=Espelid
  |first=Terje O.
  |title=Analysis of a Shellsort Algorithm
  |journal=BIT Numerical Mathematics
  |volume=13
  |issue=4
  |date=December 1973
  |pages=394–400
  |doi=10.1007/BF01933401
|s2cid=119443598
 }}  The quoted result is equation (8) on p. 399.</ref> [[Donald Knuth|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>.<ref name="Knuth" /> It follows that a two-pass Shellsort with ''h'' = Θ(''N''<sup>1/3</sup>) makes on average ''O''(''N''<sup>5/3</sup>) comparisons/inversions/running time. [[Andrew Yao|Yao]] found the average complexity of a three-pass Shellsort.<ref>{{Cite journal
  |last=Yao
  |first=Andrew Chi-Chih
  |author-link=Andrew Yao
  |title=An Analysis of (''h'', ''k'', 1)-Shellsort
  |journal=Journal of Algorithms
  |volume=1
  |issue=1
  |year=1980
  |pages=14–50
  |doi=10.1016/0196-6774(80)90003-6
  |s2cid=3054966
  |url=http://pdfs.semanticscholar.org/d569/b8a70a808c6b808ca2e25371c736ce98b14f.pdf
  |archive-url=https://web.archive.org/web/20190304043832/http://pdfs.semanticscholar.org/d569/b8a70a808c6b808ca2e25371c736ce98b14f.pdf
  |url-status=dead
  |archive-date=2019-03-04
  |id=STAN-CS-79-726
}}</ref> His result was refined by [[Svante Janson|Janson]] and Knuth:<ref>{{Cite journal
  |last1=Janson
  |first1=Svante |author1-link=Svante Janson
  |last2=Knuth
  |first2=Donald E. |author2-link=Donald Knuth
  |title=Shellsort with Three Increments
  |journal=Random Structures and Algorithms
  |volume=10
  |issue=1–2
  |year=1997
  |pages=125–142
  |doi=10.1002/(SICI)1098-2418(199701/03)10:1/2<125::AID-RSA6>3.0.CO;2-X
  |arxiv=cs/9608105
  |citeseerx=10.1.1.54.9911
  |url=http://www2.math.uu.se/~svante/papers/sj113.pdf
}}</ref> 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}{128}}g + O\left(g^{-1/2}h^{1/2}\right) + O\left(gh^{-1/2}\right)</math>. In particular, when ''h'' = Θ(''N''<sup>7/15</sup>) and ''g'' = Θ(''N''<sup>1/5</sup>), the average time of sorting is ''O''(''N''<sup>23/15</sup>).

Based on experiments, it is conjectured that Shellsort with [[Thomas N. Hibbard|Hibbard]]'s gap sequence runs in ''O''(''N''<sup>5/4</sup>) average time,<ref name="Knuth" /> and that Gonnet and Baeza-Yates's sequence requires on average 0.41''N''&nbsp;ln&nbsp;''N''&nbsp;(ln&nbsp;ln&nbsp;''N''&nbsp;+&nbsp;1/6) element moves.<ref name="Gonnet" /> Approximations of the average number of operations formerly put forward for other sequences fail when sorted arrays contain millions of elements.

The graph below shows the average number of element comparisons use by various gap sequences, divided by the [[Comparison sort#Number of comparisons required to sort a list|theoretical lower bound]], i.e. log<sub>2</sub>''N''!.  Ciuria's sequence 1, 4, 10, 23, 57, 132, 301, 701 (labelled Ci01) has been extended according to the formula <math>h_k = \lfloor2.25 h_{k-1}\rfloor</math>.

[[File:Shell sort average number of comparisons (English).svg|center]]

Applying the theory of [[Kolmogorov complexity]], Jiang, [[Ming Li|Li]], and [[Paul Vitányi|Vitányi]] 
<ref>{{Cite journal
  |last1=Jiang
  |first1=Tao
  |last2=Li
  |first2=Ming
  |author2-link=Ming Li
  |last3=Vitányi
  |first3=Paul
  |author3-link=Paul Vitányi
  |title=A Lower Bound on the Average-Case Complexity of Shellsort
  |journal=[[Journal of the ACM]]
  |volume=47
  |issue=5
  |date=September 2000
  |pages=905–911
  |doi=10.1145/355483.355488
  |citeseerx=10.1.1.6.6508
  |url=https://homepages.cwi.nl/~paulv/papers/shellsort.pdf
  |arxiv=cs/9906008
|s2cid=3265123
 }}</ref> proved the following lower bound for the order of the average number of operations/running time in a ''p''-pass Shellsort: Ω(''pN''<sup>1+1/''p''</sup>) when ''p''&nbsp;≤&nbsp;log<sub>2</sub>''N'' and Ω(''pN'') when ''p''&nbsp;>&nbsp;log<sub>2</sub>''N''.
Therefore, Shellsort has prospects of running in an average time that asymptotically grows like ''N'' log''N'' 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 [[Paul Vitányi|Vitányi]]<ref>{{cite journal
  |doi=10.1002/rsa.20737
  |last=Vitányi
  |first=Paul
  |author-link=Paul Vitányi
  |date=March 2018
  |title=On the average-case complexity of Shellsort
  |journal=Random Structures and Algorithms
  |volume=52
  |issue=2
  |pages=354–363
  |arxiv=1501.06461
  |s2cid=6833808
 |url=https://homepages.cwi.nl/~paulv/papers/shell2015.pdf
}}</ref> 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, [[Bjorn Poonen|Poonen]], and [[Torsten Suel|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>.<ref>{{Cite book
  |last1=Plaxton
  |first1=C. Greg
  |last2=Poonen
  |first2=Bjorn
  |author2-link=Bjorn Poonen
  |last3=Suel
  |first3=Torsten
  |title=Proceedings., 33rd Annual Symposium on Foundations of Computer Science
 |chapter=Improved lower bounds for Shellsort
 |author3-link=Torsten Suel
  |volume=33
  |date=24–27 October 1992
  |location=Pittsburgh, United States
  |pages=226–235
  |doi=10.1109/SFCS.1992.267769
  |isbn=978-0-8186-2900-6
  |citeseerx=10.1.1.43.1393
  |s2cid=15095863
 |chapter-url=http://engineering.nyu.edu/~suel/papers/shell.pdf
}}</ref><ref>{{Cite journal
  |last1=Plaxton
  |first1=C. Greg
  |last2=Suel
  |first2=Torsten
  |author2-link=Torsten Suel
  |title=Lower Bounds for Shellsort
  |journal=Journal of Algorithms
  |volume=23 |issue=2
  |date=May 1997
  |pages=221–240
  |doi=10.1006/jagm.1996.0825
  |citeseerx=10.1.1.460.2429
  |url=http://engineering.nyu.edu/~suel/papers/shell2.pdf
}}</ref>
Robert Cypher proved a stronger lower bound: <math>\Omega\left(N {{(\log N)^2} \over {\log\log N}}\right)</math> when <math>h_{s+1} > h_s</math> for all <math>s</math>.<ref>{{Cite journal
  |last=Cypher
  |first=Robert
  |title=A Lower Bound on the Size of Shellsort Sorting Networks
  |journal=SIAM Journal on Computing
  |volume=22
  |date=1993
  |pages=62–71
|doi=10.1137/0222006
 }}</ref>