Editing Shellsort (section)

== Gap sequences ==
The question of deciding which gap sequence to use is difficult. Every gap sequence that contains 1 yields a correct sort (as this makes the final pass an ordinary insertion sort); however, the properties of thus obtained versions of Shellsort may be very different. Too few gaps slows down the passes, and too many gaps produces an overhead.

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.

{| class="wikitable"
|- style="background-color: #efefef;"
! [[OEIS]]
! General term (''k'' ≥ 1)
! Concrete gaps
! Worst-case<br>time complexity
! Author and year of publication
|----
|
| <math>\left\lfloor\frac{N}{2^k}\right\rfloor</math>
| <math>1, 2, \ldots, \left\lfloor\frac{N}{4}\right\rfloor,
        \left\lfloor\frac{N}{2}\right\rfloor
  </math>
| <math>\Theta\left(N^2\right)</math> [e.g. when ''N'' = 2<sup>''p''</sup>]
| [[Donald Shell|Shell]], 1959<ref name="Shell"/>
|----
|
| <math>2 \left\lfloor\frac{N}{2^{k+1}}\right\rfloor + 1</math>
| <math>1, 3, \ldots, \; 2 \left\lfloor\frac{N}{8}\right\rfloor + 1,
        \; \; 2 \left\lfloor\frac{N}{4}\right\rfloor + 1
  </math>
| <math>\Theta\left(N^\frac{3}{2}\right)</math>
| Frank & Lazarus, 1960<ref>{{Cite journal
  |last1=Frank
  |first1=R. M.
  |last2=Lazarus
  |first2=R. B.
  |title=A High-Speed Sorting Procedure
  |journal=Communications of the ACM
  |volume=3
  |issue=1
  |year=1960
  |pages=20–22
  |doi=10.1145/366947.366957|s2cid=34066017
 |doi-access=free
  }}</ref>
|----
| {{OEIS link|A000225}}
| <math>2^k - 1</math>
| <math>1, 3, 7, 15, 31, 63, \ldots</math>
| <math>\Theta\left(N^\frac{3}{2}\right)</math>
| [[Thomas N. Hibbard|Hibbard]], 1963<ref>{{Cite journal
  |last=Hibbard
  |first=Thomas N.
  |title=An Empirical Study of Minimal Storage Sorting
  |journal=Communications of the ACM
  |volume=6
  |issue=5
  |year=1963
  |pages=206–213
  |doi=10.1145/366552.366557|s2cid=12146844
 |doi-access=free
  }}</ref>
|----
| {{OEIS link|A083318}}
| <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<ref>{{Cite journal
  |url=http://www.mathnet.ru/links/83f0a81df1ec06f76d3683c6cab7d143/ppi751.pdf
  |last1=Papernov
  |first1=A. A.
  |last2=Stasevich
  |first2=G. V.
  |title=A Method of Information Sorting in Computer Memories
  |journal=Problems of Information Transmission
  |volume=1
  |issue=3
  |year=1965
  |pages=63–75}}</ref>
|----
| {{OEIS link|A003586}}
| 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>
| [[Vaughan Ronald Pratt|Pratt]], 1971<ref name="Pratt"/>
|----
| {{OEIS link|A003462}}
| <math>\frac{3^k - 1}{2}</math>, not greater than <math>\left\lceil\frac{N}{3}\right\rceil</math>
| <math>1, 4, 13, 40, 121, \ldots </math>
| <math>\Theta\left(N^\frac{3}{2}\right)</math>
| [[Donald Knuth|Knuth]], 1973,<ref name="Knuth">{{Cite book
  |last=Knuth
  |first=Donald E. |author-link=Donald Knuth
  |title=The Art of Computer Programming. Volume 3: Sorting and Searching
  |edition=2nd
  |publisher=Addison-Wesley
  |location=Reading, Massachusetts
  |year=1997
  |pages=83–95
  |chapter=Shell's method
  |isbn=978-0-201-89685-5}}</ref> based on [[Vaughan Ronald Pratt|Pratt]], 1971<ref name="Pratt"/>
|----
| {{OEIS link|A036569}}
| <math>\begin{align}
           &\prod\limits_I a_q, \hbox{where} \\
  a_0 = {} &3 \\
  a_q = {} &\min\left\{n \in \mathbb{N}\colon n \ge \left(\frac{5}{2}\right)^{q+1}, \forall p\colon 0 \le p < q \Rightarrow \gcd(a_p, n) = 1\right\} \\
    I = {} &\left\{0 \le q < r \mid q \neq \frac{1}{2}\left(r^2 + r\right) - k \right\} \\
    r = {} &\left\lfloor \sqrt{2k + \sqrt{2k}} \right\rfloor
\end{align}</math>
| <math>1, 3, 7, 21, 48, 112, \ldots</math>
| <math>O\left(N^{1 + \sqrt{\frac{8\ln\left(5/2\right)}{\ln(N)}}}\right)</math>
| Incerpi & [[Robert Sedgewick (computer scientist)|Sedgewick]], 1985,<ref>{{Cite journal
  |last1=Incerpi
  |first1=Janet
  |last2=Sedgewick
  |first2=Robert |author2-link=Robert Sedgewick (computer scientist)
  |title=Improved Upper Bounds on Shellsort
  |journal=Journal of Computer and System Sciences
  |volume=31
  |issue=2
  |year=1985
  |pages=210–224
  |doi=10.1016/0022-0000(85)90042-x|url=https://hal.inria.fr/inria-00076291/file/RR-0267.pdf
  }}</ref> [[Donald Knuth|Knuth]]<ref name="Knuth"/>
|----
| {{OEIS link|A036562}}
| <math>4^k + 3 \cdot 2^{k-1} + 1</math>, prefixed with 1
| <math>1, 8, 23, 77, 281, \ldots</math>
| <math>O\left(N^\frac{4}{3}\right)</math>
| Sedgewick, 1982<ref name="Sedgewick"/>
|----
| {{OEIS link|A033622}}
| <math>\begin{cases}
  9\left(2^{k} - 2^\frac{k}{2}\right) + 1 & k\text{ even}, \\
  8 \cdot 2^{k} - 6 \cdot 2^{(k+1)/2} + 1         & k\text{ odd}
\end{cases}</math>
| <math>1, 5, 19, 41, 109, \ldots</math>
| <math>O\left(N^\frac{4}{3}\right)</math>
| Sedgewick, 1986<ref name="Sedgewick2">
  {{Cite journal
   |last=Sedgewick
   |first=Robert |author-link=Robert Sedgewick (computer scientist)
   |title=A New Upper Bound for Shellsort
   |journal=Journal of Algorithms
   |volume=7
   |issue=2
   |year=1986
   |pages=159–173
   |doi=10.1016/0196-6774(86)90001-5
  }}</ref>
|----
| 
| <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>
| {{unk}}
| [[Gaston Gonnet|Gonnet]] & [[Ricardo Baeza-Yates|{{nowrap|Baeza-Yates}}]], 1991<ref name="Gonnet">{{Cite book
  |last1=Gonnet
  |first1=Gaston H.
  |last2=Baeza-Yates
  |first2=Ricardo
  |title=Handbook of Algorithms and Data Structures: In Pascal and C
  |publisher=Addison-Wesley
  |location=Reading, Massachusetts
  |edition=2nd
  |year=1991
  |pages=161–163
  |chapter=Shellsort
  |isbn=978-0-201-41607-7
  |quote=Extensive experiments indicate that the sequence defined by {{math|1=''&alpha;'' = 0.45454 < 5/11}} performs significantly better than other sequences. The easiest way to compute {{math|{{floor|0.45454''n''}}}} is by <code>(5 * ''n'' — 1)/11</code> using integer arithmetic.
}}</ref>
|----
| {{OEIS link|A108870}}
| <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>
| {{unk}}
| Tokuda, 1992<ref>{{Cite book
  |editor-last=van Leeuven
  |editor-first=Jan
  |chapter=An Improved Shellsort
  |last=Tokuda
  |first=Naoyuki
  |title=Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture
  |publisher=North-Holland Publishing Co.
  |location=Amsterdam
  |year=1992
  |pages=449–457
  |isbn=978-0-444-89747-3}}</ref> (misquote per OEIS)
|----
| {{OEIS link|A102549}}
| Unknown (experimentally derived)
| <math>1, 4, 10, 23, 57, 132, 301, 701</math><!--Please don't add 1750. It doesn't belong here.-->
| {{unk}}
| Ciura, 2001<ref name=":0">{{Cite book
  |chapter-url=http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf
  |archive-url=https://web.archive.org/web/20180923235211/http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf
  |archive-date=23 September 2018
  |title=Proceedings of the 13th International Symposium on Fundamentals of Computation Theory
  |editor-last=Freiwalds
  |editor-first=Rusins
  |last=Ciura
  |first=Marcin
  |chapter=Best Increments for the Average Case of Shellsort
  |publisher=Springer-Verlag
  |location=London
  |year=2001
  |pages=106–117
  |isbn=978-3-540-42487-1}}</ref>
|----
| {{OEIS link|A366726}}
| <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>
| {{unk}}
| Lee, 2021<ref>{{cite arXiv
 | last       = Lee
 | first      = Ying Wai
 | eprint     = 2112.11112
 | title      = Empirically Improved Tokuda Gap Sequence in Shellsort
 | class      = cs.DS
 | date       = 21 December 2021
 }}</ref>
|----
| 
| <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>
| {{unk}}
| Skean, Ehrenborg, Jaromczyk, 2023<ref>{{cite arXiv
 | first1     = Oscar
 | last1      = Skean
 | first2     = Richard
 | last2      = Ehrenborg
 | first3     = Jerzy W.
 | last3      = Jaromczyk
 | eprint     = 2301.00316
 | title      = Optimization Perspectives on Shellsort
 | class      = cs.DS
 | date       = 1 Jan 2023
 }}</ref>
|-
|
|Start at 1.  Successive increments are smallest prime <math>  \geq 3  </math> times previous
|<math>1, 3, 11, 37, 113, 347, 1049, \ldots</math>
|{{unk}}
|Glenn C. Rhoads<ref>{{Cite web |last=Rhoads |first=Glenn |date=March 1, 2010 |title=Shellsort Increment Sequences |url=https://gcrhoads.byethost4.com/shellSort.html |url-status=live |access-date=May 13, 2025 |website=The Glenn}}</ref>
|}
When the binary representation of ''N'' contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(''N''<sup>2</sup>) 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''(''N''&nbsp;log&nbsp;''N'') that is optimal for comparison sorts, Pratt's version lends itself to [[sorting network]]s 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.<ref name="Gonnet"/> 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 using gaps which have low [[greatest common divisor]]s or are pairwise [[coprime]].<ref>{{Cite book
  |title=Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching
  |last=Sedgewick
  |first=Robert |author-link=Robert Sedgewick (computer scientist)
  |chapter=Shellsort
  |publisher=Addison-Wesley
  |location=Reading, Massachusetts
  |year=1998
  |pages=285–292
  |isbn=978-0-201-35088-3}}</ref>{{Fv|date=February 2021|reason=There's a lot of discussion of divisibility, but I couldn't find this explicitly stated.  E.g. p.&nbsp;289 says &quot;The increment sequences that we have discussed to this point are effective because successive elements are relatively prime. Another family of increment sequences is effective precisely because successive elements are not relatively prime.&quot;}} Gaps which are odd numbers seem to work well in practice: 25% reductions have been observed by avoiding even-numbered gaps. Gaps which avoid multiples of 3 and 5 seem to produce small benefits of < 10%.{{OR|date=May 2023}}

With respect to the average number of comparisons, Ciura's sequence<ref name=":0" /> has the best known performance; gaps greater than 701 were not determined but the sequence can be further extended according to the recursive formula <math>h_k = \lfloor 2.25 h_{k-1} \rfloor</math>.

Tokuda's sequence, defined by the simple formula <math>h_k = \lceil h'_k \rceil</math>, where <math>h'_k = 2.25 h'_{k-1} + 1</math>, <math>h'_1 = 1</math>, can be recommended for practical applications.

If the maximum input size is small, as may occur if Shellsort is used on small subarrays by another recursive sorting algorithm such as [[quicksort]] or [[merge sort]], then it is possible to tabulate an optimal sequence for each input size.<ref>{{cite web
 |title=How to choose the lengths of my sub sequences for a shell sort?
 |first=Olof |last=Forshell
 |date=22 May 2018
 |url=https://stackoverflow.com/a/50470237
 |website=[[Stack Overflow]]
}}  Additional commentary at [https://stackoverflow.com/a/50490873#50490873 Fastest gap sequence for shell sort?] (23 May 2018).</ref><ref>{{cite arXiv
 |title=Optimal Gap Sequences in Shellsort for {{math|''n'' ≤ 16}} Elements 
 |first=Ying Wai |last=Lee
 |date=21 December 2021
 |eprint=2112.11127
 |class=math.CO
}}</ref>