Shellsort
Sorting algorithm which uses multiple comparison intervals
title: "Shellsort" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["comparison-sorts"] description: "Sorting algorithm which uses multiple comparison intervals" topic_path: "general/comparison-sorts" source: "https://en.wikipedia.org/wiki/Shellsort" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Sorting algorithm which uses multiple comparison intervals ::
::data[format=table title="Infobox Algorithm"]
| Field | Value |
|---|---|
| class | Sorting algorithm |
| image | [[File:Sorting shellsort anim.gif |
| caption | Shellsort with gaps 23, 10, 4, 1 in action |
| data | Array |
| time | O(n2) (worst known worst case gap sequence) |
| O(n log2n) (best known worst case gap sequence){{Cite book | |
| last | Pratt |
| first | Vaughan Ronald |
| 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}} |
| best-time | O(n log n) (most gap sequences) |
| O(n log2n) (best known worst-case gap sequence) | |
| average-time | depends on gap sequence |
| space | О(n) total, O(1) auxiliary |
| optimal | No |
| :: |
|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 |time=O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence){{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}} |best-time=O(n log n) (most gap sequences) O(n log2n) (best known worst-case gap sequence) |average-time=depends on gap sequence |space=О(n) total, O(1) auxiliary |optimal=No ::figure[src="https://upload.wikimedia.org/wikipedia/commons/4/4c/Shell_sorting_algorithm_color_bars.svg" caption="Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1" alt="The steps of Shellsort."] ::
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be understood as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). 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.{{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
Description
Shellsort is an optimization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, taking every hth element produces a sorted list. Such a list is said to be h-sorted. It can also be thought of as h interleaved lists, each individually sorted. |last=Sedgewick |first=Robert |author-link=Robert Sedgewick (computer scientist) |title=Algorithms in C |edition=3rd |volume=1 |publisher=Addison-Wesley |year=1998 |pages=273–281 |isbn=978-0-201-31452-6 |url-access=registration |url=https://archive.org/details/algorithmsinc00sedg/page/273 |last1=Kernighan |first1=Brian W. |author-link1=Brian Kernighan |last2=Ritchie |first2=Dennis M. |author-link2=Dennis Ritchie |title=The C Programming Language |edition=2nd |publisher=Prentice Hall |year=1996 |pages=62 |isbn=978-7-302-02412-5
In simplistic terms, this means if we have an array of 1024 numbers, our first gap (h) could be 512. We then run through the list comparing each element in the first half to the element in the second half. Our second gap (k) is 256, which breaks the array into four sections (starting at 0, 256, 512, 768), and we make sure the first items in each section are sorted relative to each other, then the second item in each section, and so on. In practice the gap sequence could be anything, but the last gap is always 1 to finish the sort (effectively finishing with an ordinary insertion sort).
An example run of Shellsort with gaps 5, 3 and 1 is shown below.
::data[format=table] | a1 || a2 || a3 || a4 | a5 || a6 || a7 || a8 | a9 || a10 || a11 || a12 | Input data | After 5-sorting | After 3-sorting | After 1-sorting | |---|---|---|---|---|---|---| | 62 | 83 | 18 | 53 | 07 | 17 | 95 | | 17 | 28 | 18 | 47 | 07 | 25 | 83 | | 17 | 07 | 18 | 47 | 28 | 25 | 69 | | 07 | 17 | 18 | 25 | 28 | 47 | 53 | ::
The first pass, 5-sorting, performs insertion sort on five separate subarrays (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). For instance, it changes the subarray (a1, a6, a11) from (62, 17, 25) to (17, 25, 62). The next pass, 3-sorting, performs insertion sort on the three subarrays (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). The last pass, 1-sorting, is an ordinary insertion sort of the entire array (a1,..., a12).
As the example illustrates, the subarrays that Shellsort operates on are initially short; later they are longer but almost ordered. In both cases insertion sort works efficiently.
Unlike insertion sort, Shellsort is not a stable sort since gapped insertions transport equal elements past one another and thus lose their original order. It is an adaptive sorting algorithm in that it executes faster when the input is partially sorted.
Example
This is a C# example using Marcin Ciura's gap sequence, with an inner insertion sort. ::code[lang=csharp] using System.Collections.Generic;
// Sort an array a[0...n-1]. List
// Start with the largest gap and work down to a gap of 1 // similar to insertion sort but instead of 1, gap is being used in each step foreach (int gap in gaps) { // Do a gapped insertion sort for every element in gaps // Each loop leaves a[0..gap-1] in gapped order for (int i = gap; i < n; ++i) { // save a[i] in temp and make a hole at position i int temp = a[i]; // shift earlier gap-sorted elements up until the correct location for a[i] is found for (int j = i; (j >= gap) && (a[j - gap] > temp); j -= gap) { a[j] = a[j - gap]; } // put temp (the original a[i]) in its correct location a[j] = temp; } } ::
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.
::data[format=table] | OEIS | General term (k ≥ 1) | Concrete gaps | Worst-case time complexity | Author and year of publication | |---|---|---|---|---| | | \left\lfloor\frac{N}{2^k}\right\rfloor | 1, 2, \ldots, \left\lfloor\frac{N}{4}\right\rfloor, | \Theta\left(N^2\right) [e.g. when N = 2p] | Shell, 1959 | | | 2 \left\lfloor\frac{N}{2^{k+1}}\right\rfloor + 1 | 1, 3, \ldots, ; 2 \left\lfloor\frac{N}{8}\right\rfloor + 1, | \Theta\left(N^\frac{3}{2}\right) | Frank & Lazarus, 1960{{Cite journal | | | 2^k - 1 | 1, 3, 7, 15, 31, 63, \ldots | \Theta\left(N^\frac{3}{2}\right) | Hibbard, 1963{{Cite journal | | | 2^k + 1, prefixed with 1 | 1, 3, 5, 9, 17, 33, 65, \ldots | \Theta\left(N^\frac{3}{2}\right) | Papernov & Stasevich, 1965{{Cite journal | | | Successive numbers of the form 2^p 3^q (3-smooth numbers) | 1, 2, 3, 4, 6, 8, 9, 12, \ldots | \Theta\left(N \log^2 N\right) | Pratt, 1971 | | | \frac{3^k - 1}{2}, not greater than \left\lceil\frac{N}{3}\right\rceil | 1, 4, 13, 40, 121, \ldots | \Theta\left(N^\frac{3}{2}\right) | Knuth, 1973,{{Cite book | | | \begin{align} | 1, 3, 7, 21, 48, 112, \ldots | O\left(N^{1 + \sqrt{\frac{8\ln\left(5/2\right)}{\ln(N)}}}\right) | Incerpi & Sedgewick, 1985,{{Cite journal | | | 4^k + 3 \cdot 2^{k-1} + 1, prefixed with 1 | 1, 8, 23, 77, 281, \ldots | O\left(N^\frac{4}{3}\right) | Sedgewick, 1982 | | | \begin{cases} | 1, 5, 19, 41, 109, \ldots | O\left(N^\frac{4}{3}\right) | Sedgewick, 1986 | | | h_k = \max\left{\left\lfloor \frac{5h_{k-1}-1}{11} \right\rfloor, 1\right}, h_0 = N | 1, \ldots, \left\lfloor \frac{5}{11}\left\lfloor \frac{5N-1}{11} \right\rfloor-\frac{1}{11}\right\rfloor, | | Gonnet & Baeza-Yates, 1991{{Cite book | | | \left\lceil \frac{1}{5} \left(9\cdot \left(\frac{9}{4}\right)^{k-1} - 4 \right) \right\rceil (or equivalently, \left\lceil \frac{\left(9/4\right)^k-1}{\left(9/4\right)-1} \right\rceil) | 1, 4, 9, 20, 46, 103, \ldots | | Tokuda, 1992{{Cite book | | | Unknown (experimentally derived) | 1, 4, 10, 23, 57, 132, 301, 701 | | Ciura, 2001{{Cite book | | | \left\lceil \frac{\gamma^k-1}{\gamma-1} \right\rceil, \gamma = 2.243609061420001\ldots | 1, 4, 9, 20, 45, 102, 230, 516, \ldots | | Lee, 2021{{cite arXiv | | | \left\lfloor 4.0816\cdot 8.5714^{\frac{k}{2.2449}} \right\rfloor | 1, 4, 10, 27, 72, 187, 488, \ldots | | Skean, Ehrenborg, Jaromczyk, 2023{{cite arXiv | | | Start at 1. Successive increments are smallest prime \geq 3 times previous | 1, 3, 11, 37, 113, 347, 1049, \ldots | | Glenn C. Rhoads | ::
When the binary representation of N contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(N2) 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 log N) that is optimal for comparison sorts, Pratt's version lends itself to sorting networks 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. 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 divisors or are pairwise coprime.{{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}} 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
With respect to the average number of comparisons, Ciura's sequence has the best known performance; gaps greater than 701 were not determined but the sequence can be further extended according to the recursive formula h_k = \lfloor 2.25 h_{k-1} \rfloor.
Tokuda's sequence, defined by the simple formula h_k = \lceil h'_k \rceil, where h'k = 2.25 h'{k-1} + 1, h'_1 = 1, 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.{{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 |title=Optimal Gap Sequences in Shellsort for n ≤ 16 Elements |first=Ying Wai |last=Lee |date=21 December 2021 |eprint=2112.11127 |class=math.CO
Computational complexity
The following property holds: after h2-sorting of any h1-sorted array, the array remains h1-sorted.{{Cite journal |last1=Gale |first1=David |author-link=David Gale |last2=Karp |first2=Richard M. |author2-link=Richard M. Karp |title=A Phenomenon in the Theory of Sorting |journal=Journal of Computer and System Sciences |volume=6 |issue=2 |date=April 1972 |pages=103–115 |doi=10.1016/S0022-0000(72)80016-3 |url=https://core.ac.uk/download/pdf/82277625.pdf |doi-access=free |last=Selmer |first=Ernst S. |author-link=Ernst Sejersted Selmer |title=On Shellsort and the Frobenius Problem |journal=BIT Numerical Mathematics |volume=29 |issue=1 |date=March 1989 |pages=37–40 |doi=10.1007/BF01932703 |hdl=1956/19572 |s2cid=32467267 |hdl-access=free |url=https://bora.uib.no/bora-xmlui/bitstream/handle/1956/19572/On%20Shellsort%20and%20the%20Frobenius%20problem.pdf
Mark Allen Weiss proved that Shellsort runs in O(N log N) time when the input array is in reverse order.{{Cite journal |last=Weiss |first=Mark Allen |title=A good case for Shellsort |journal=Congressus Numerantium |volume=73 |date=1989 |pages=59–62
With respect to the average number of operations, none of the proven results concerns a practical gap sequence. For gaps that are powers of two, Espelid computed this average as 0.5349N\sqrt{N}-0.4387N-0.097\sqrt{N}+O(1).{{Cite journal |last=Espelid |first=Terje O. |title=Analysis of a Shellsort Algorithm |journal=BIT Numerical Mathematics |volume=13 |issue=4 |date=December 1973 |pages=394–400 |doi=10.1007/BF01933401 |s2cid=119443598 |last=Yao |first=Andrew Chi-Chih |author-link=Andrew Yao |title=An Analysis of (h, k, 1)-Shellsort |journal=Journal of Algorithms |volume=1 |issue=1 |year=1980 |pages=14–50 |doi=10.1016/0196-6774(80)90003-6 |s2cid=3054966 |url=http://pdfs.semanticscholar.org/d569/b8a70a808c6b808ca2e25371c736ce98b14f.pdf |archive-url=https://web.archive.org/web/20190304043832/http://pdfs.semanticscholar.org/d569/b8a70a808c6b808ca2e25371c736ce98b14f.pdf |url-status=dead |archive-date=2019-03-04 |id=STAN-CS-79-726 |last1=Janson |first1=Svante |author1-link=Svante Janson |last2=Knuth |first2=Donald E. |author2-link=Donald Knuth |title=Shellsort with Three Increments |journal=Random Structures and Algorithms |volume=10 |issue=1–2 |year=1997 |pages=125–142 |doi=10.1002/(SICI)1098-2418(199701/03)10:1/23.0.CO;2-X |arxiv=cs/9608105 |citeseerx=10.1.1.54.9911 |url=http://www2.math.uu.se/~svante/papers/sj113.pdf
Based on experiments, it is conjectured that Shellsort with Hibbard's gap sequence runs in O(N5/4) average time, and that Gonnet and Baeza-Yates's sequence requires on average 0.41N ln N (ln ln N + 1/6) element moves. Approximations of the average number of operations formerly put forward for other sequences fail when sorted arrays contain millions of elements.
The graph below shows the average number of element comparisons use by various gap sequences, divided by the theoretical lower bound, i.e. log2N!. Ciuria's sequence 1, 4, 10, 23, 57, 132, 301, 701 (labelled Ci01) has been extended according to the formula h_k = \lfloor2.25 h_{k-1}\rfloor.
::figure[src="https://upload.wikimedia.org/wikipedia/commons/f/fe/Shell_sort_average_number_of_comparisons_(English).svg"] ::
Applying the theory of Kolmogorov complexity, Jiang, Li, and Vitányi |last1=Jiang |first1=Tao |last2=Li |first2=Ming |author2-link=Ming Li |last3=Vitányi |first3=Paul |author3-link=Paul Vitányi |title=A Lower Bound on the Average-Case Complexity of Shellsort |journal=Journal of the ACM |volume=47 |issue=5 |date=September 2000 |pages=905–911 |doi=10.1145/355483.355488 |citeseerx=10.1.1.6.6508 |url=https://homepages.cwi.nl/~paulv/papers/shellsort.pdf |arxiv=cs/9906008 |s2cid=3265123 Therefore, Shellsort has prospects of running in an average time that asymptotically grows like N logN only when using gap sequences whose number of gaps grows in proportion to the logarithm of the array size. It is, however, unknown whether Shellsort can reach this asymptotic order of average-case complexity, which is optimal for comparison sorts. The lower bound was improved by Vitányi{{cite journal |doi=10.1002/rsa.20737 |last=Vitányi |first=Paul |author-link=Paul Vitányi |date=March 2018 |title=On the average-case complexity of Shellsort |journal=Random Structures and Algorithms |volume=52 |issue=2 |pages=354–363 |arxiv=1501.06461 |s2cid=6833808 |url=https://homepages.cwi.nl/~paulv/papers/shell2015.pdf \Omega ( N\sum_{k=1}^p h_{k-1}/h_k ) where h_0=N. This result implies for example the Jiang-Li-Vitányi lower bound for all p-pass increment sequences and improves that lower bound for particular increment sequences. In fact all bounds (lower and upper) currently known for the average case are precisely matched by this lower bound. For example, this gives the new result that the Janson-Knuth upper bound is matched by the resulting lower bound for the used increment sequence, showing that three pass Shellsort for this increment sequence uses \Theta(N^{23/15}) comparisons/inversions/running time. The formula allows us to search for increment sequences that yield lower bounds which are unknown; for example an increment sequence for four passes which has a lower bound greater than \Omega(pn^{1+1/p}) = \Omega(n^{5/4}) for the increment sequence h_1 = n^{11/16}, h_2 = n^{7/16}, h_3 = n^{3/16}, h_4 = 1. The lower bound becomes T = \Omega(n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3/16}) = \Omega(n^{1+5/16}) = \Omega(n^{21/16}).
The worst-case complexity of any version of Shellsort is of higher order: Plaxton, Poonen, and Suel showed that it grows at least as rapidly as \Omega\left(N \left( {\log N \over \log \log N} \right)^2\right).{{Cite book |last1=Plaxton |first1=C. Greg |last2=Poonen |first2=Bjorn |author2-link=Bjorn Poonen |last3=Suel |first3=Torsten |title=Proceedings., 33rd Annual Symposium on Foundations of Computer Science |chapter=Improved lower bounds for Shellsort |author3-link=Torsten Suel |volume=33 |date=24–27 October 1992 |location=Pittsburgh, United States |pages=226–235 |doi=10.1109/SFCS.1992.267769 |isbn=978-0-8186-2900-6 |citeseerx=10.1.1.43.1393 |s2cid=15095863 |chapter-url=http://engineering.nyu.edu/~suel/papers/shell.pdf |last1=Plaxton |first1=C. Greg |last2=Suel |first2=Torsten |author2-link=Torsten Suel |title=Lower Bounds for Shellsort |journal=Journal of Algorithms |volume=23 |issue=2 |date=May 1997 |pages=221–240 |doi=10.1006/jagm.1996.0825 |citeseerx=10.1.1.460.2429 |url=http://engineering.nyu.edu/~suel/papers/shell2.pdf Robert Cypher proved a stronger lower bound: \Omega\left(N \right) when h_{s+1} h_s for all s.{{Cite journal |last=Cypher |first=Robert |title=A Lower Bound on the Size of Shellsort Sorting Networks |journal=SIAM Journal on Computing |volume=22 |date=1993 |pages=62–71 |doi=10.1137/0222006
Applications
Shellsort performs more operations and has higher cache miss ratio than quicksort. However, since it can be implemented using little code and does not use the call stack, some implementations of the qsort function in the C standard library targeted at embedded systems use it instead of quicksort. Shellsort is, for example, used in the uClibc library.{{Cite web | url=http://git.uclibc.org/uClibc/tree/libc/stdlib/stdlib.c#n700 | title=libc/stdlib/stdlib.c | first=Manuel III |last=Novoa | access-date=2014-10-29}} For similar reasons, in the past, Shellsort was used in the Linux kernel.{{Cite web | url=https://github.com/torvalds/linux/blob/72932611b4b05bbd89fafa369d564ac8e449809b/kernel/groups.c#L105 | title=kernel/groups.c | website=GitHub | access-date=2012-05-05}}
Shellsort can also serve as a sub-algorithm of introspective sort, to sort short subarrays and to prevent a slowdown when the recursion depth exceeds a given limit. This principle is employed, for instance, in the bzip2 compressor.{{Cite web |url=https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/lxr/source/src/util/compress/bzip2/blocksort.c#L519 |title=bzip2/blocksort.c |author=Julian Seward |access-date=2011-03-30}}
References
Bibliography
- {{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 |title-link=The Art of Computer Programming }}
- Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.
References
- "Shellsort & Comparisons".
- "Shell sort". National Institute of Standards and Technology.
- Rhoads, Glenn. (March 1, 2010). "Shellsort Increment Sequences".
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::