Shellsort

Shellsort
Step-by-step visualisation of Shellsort
Shellsort with gaps 23, 10, 4, 1 in action
ClassSorting algorithm
Data structureArray
Worst-case performanceO(n2) (worst known worst case gap sequence)
O(n log2n) (best known worst case gap sequence)[1]
Best-case performanceO(n log n) (most gap sequences)
O(n log2n) (best known worst-case gap sequence)[2]
Average performancedepends on gap sequence
Worst-case space complexityО(n) total, O(1) auxiliary
OptimalNo
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 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.

  1. ^ 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.
  2. ^ "Shellsort & Comparisons". Archived from the original on 20 December 2019. Retrieved 14 November 2015.
  3. ^ Cite error: The named reference Knuth was invoked but never defined (see the help page).
  4. ^ 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.
  5. ^ 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.