Editing Shellsort (section)

{{Short description|Sorting algorithm which uses multiple comparison intervals}}
{{Infobox Algorithm
 |class=[[Sorting algorithm]]
 |image=[[File:Sorting shellsort anim.gif|Step-by-step visualisation of Shellsort]]
 |caption=Shellsort with gaps 23, 10, 4, 1 in action
 |data=[[Array data structure|Array]]
 |time=O(''n''<sup>2</sup>) (worst known worst case gap sequence)<br />O(''n'' log<sup>2</sup>''n'') (best known worst case gap sequence)<ref name="Pratt">{{Cite book
  |last=Pratt
  |first=Vaughan Ronald |author-link=Vaughan Ronald Pratt
  |year=1979
  |publisher=Garland
  |title=Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)
  |url=https://apps.dtic.mil/sti/pdfs/AD0740110.pdf
  |archive-url=https://web.archive.org/web/20210907132436/https://apps.dtic.mil/sti/pdfs/AD0740110.pdf
  |url-status=live
  |archive-date=7 September 2021
  |isbn=978-0-8240-4406-0}}</ref>
 |best-time=O(''n'' log ''n'') (most gap sequences)<br>O(''n'' log<sup>2</sup>''n'') (best known worst-case gap sequence)<ref>{{cite web |title=Shellsort & Comparisons |url=http://www.cs.wcupa.edu/rkline/ds/shell-comparison.html |access-date=14 November 2015 |archive-date=20 December 2019 |archive-url=https://web.archive.org/web/20191220040546/https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html |url-status=dead }}</ref>
 |average-time=depends on gap sequence
 |space=О(''n'') total, O(1) auxiliary
 |optimal=No
}}
[[File:Shell sorting algorithm color bars.svg|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 algorithm|in-place]] [[comparison sort]]. It can be understood as either a generalization of sorting by exchange ([[bubble sort]]) or sorting by insertion ([[insertion sort]]).<ref name="Knuth" /> The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange. 
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]].

The algorithm was first published by [[Donald Shell]] in 1959, and has nothing to do with shells.<ref name="Shell">{{Cite journal
  |url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
  |last=Shell
  |first=D. L.
  |title=A High-Speed Sorting Procedure
  |journal=Communications of the ACM
  |volume=2
  |issue=7
  |year=1959
  |pages=30–32
  |doi=10.1145/368370.368387
  |s2cid=28572656
  |access-date=18 October 2011
  |archive-date=30 August 2017
  |archive-url=https://web.archive.org/web/20170830020037/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
  |url-status=dead
  }}</ref><ref>Some older textbooks and references call this the "Shell–Metzner" sort after [[Marlene Metzner Norton]], but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it." See {{Cite web |title=Shell sort |url=https://xlinux.nist.gov/dads/HTML/shellsort.html |access-date=2007-07-17 |publisher=National Institute of Standards and Technology}}</ref>