Editing Sorting algorithm (section)

==== Shellsort ====
[[File:Shell_sorting_algorithm_color_bars.svg|right|thumb|A Shellsort, different from bubble sort in that it moves elements to numerous [[Swap (computer science)|swapping positions]].]]
{{Main|Shellsort}}
''Shellsort'' was invented by [[Donald Shell]] in 1959.<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=2020-03-23
  |archive-date=2017-08-30
  |archive-url=https://web.archive.org/web/20170830020037/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
  |url-status=dead
  }}</ref> It improves upon insertion sort by moving out of order elements more than one position at a time. The concept behind Shellsort is that insertion sort performs in {{tmath|O(kn)}} time, where k is the greatest distance between two out-of-place elements. This means that generally, they perform in ''O''(''n''<sup>2</sup>), but for data that is mostly sorted, with only a few elements out of place, they perform faster. So, by first sorting elements far away, and progressively shrinking the gap between the elements to sort, the final sort computes much faster. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort.

The worst-case time complexity of Shellsort is an [[open problem]] and depends on the gap sequence used, with known complexities ranging from ''O''(''n''<sup>2</sup>) to ''O''(''n''<sup>4/3</sup>) and Θ(''n'' log<sup>2</sup> ''n''). This, combined with the fact that Shellsort is [[in-place]], only needs a relatively small amount of code, and does not require use of the [[call stack]], makes it is useful in situations where memory is at a premium, such as in [[embedded system]]s and [[operating system kernel]]s.