Sorting algorithm which uses multiple comparison intervals
Shellsort
Shellsort with gaps 23, 10, 4, 1 in action
Class
Sorting algorithm
Data structure
Array
Worst-case performance
O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)[1]
Best-case performance
O(n log n) (most gap sequences) O(n log2n) (best known worst-case gap sequence)[2]
Average performance
depends on gap sequence
Worst-case space complexity
О(n) total, O(1) auxiliary
Optimal
No
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 seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort).[3] 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. Donald Shell published the first version of this sort in 1959.[4][5] 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.
^Pratt, Vaughan Ronald (1979). Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)(PDF). Garland. ISBN 978-0-8240-4406-0. Archived (PDF) from the original on 7 September 2021.
^"Shellsort & Comparisons". Archived from the original on 20 December 2019. Retrieved 14 November 2015.
^Cite error: The named reference Knuth was invoked but never defined (see the help page).
^Shell, D. L. (1959). "A High-Speed Sorting Procedure" (PDF). Communications of the ACM. 2 (7): 30–32. doi:10.1145/368370.368387. S2CID 28572656. Archived from the original (PDF) on 30 August 2017. Retrieved 18 October 2011.
^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 "Shell sort". National Institute of Standards and Technology. Retrieved 17 July 2007.
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange...
is expensive, requiring shifting all following elements over by one. Shellsort is a variant of insertion sort that is more efficient for larger lists...
Richard Box in 1991. Comb sort improves on bubble sort in the same way that Shellsort improves on insertion sort, in that they both allow elements that start...
designed the Shellsort sorting algorithm. He acquired his Ph.D. in mathematics from the University of Cincinnati in 1959, and published the Shellsort algorithm...
numbers? What is the lowest possible average-case time complexity of Shellsort with a deterministic, fixed gap sequence? Can 3SUM be solved in strongly...
scores other than 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 and 7–1 are possible. The Shellsort algorithm is a sorting algorithm whose time complexity is currently an...
account on a remote server Secure Shell, cryptographic network protocol Shellsort or Shell sort, a sorting algorithm by Donald Shell Shell, an empty expert...
(worst-case) bound on some usually faster sorting algorithms such as quicksort, Shellsort, and tree sort O ( n c ) {\displaystyle O(n^{c})} polynomial or algebraic...
366957. S2CID 34066017. Sedgewick, Robert (1986). "A New Upper Bound for Shellsort". Journal of Algorithms. 7 (2): 159–173. doi:10.1016/0196-6774(86)90001-5...
supervision of advisor Donald Knuth. His thesis focused on analysis of the Shellsort sorting algorithm and sorting networks. Pratt was an assistant professor...
unsorted segments. On return to England, he was asked to write code for Shellsort. Hoare mentioned to his boss that he knew of a faster algorithm and his...
Society 15 (2002), 857–892. Poonen, Bjorn (1993). "The Worst Case in Shellsort and Related Algorithms". Journal of Algorithms. 15 (1). Elsevier BV: 101–124...
two-pass Shellsort and an upper bound of O ( n 23 / 15 ) {\displaystyle O(n^{23/15})} for a particular increment sequence for three-pass Shellsort were established...
footballer (Arsenal). Donald Shell, 91, American computer scientist (Shellsort). Barbara Snelling, 87, American politician, Vermont Lieutenant Governor...
Global Information
