Shellsort

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be
Shellsort
understood 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.

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.[6]
Beginning with large values of h allows elements to move long distances in the original list, reducing large
amounts of disorder quickly, and leaving less work for smaller h-sort steps to do.[7] If the list is then k-sorted
for some smaller integer k, then the list remains h-sorted. A final sort with h = 1 ensures the list is fully
sorted at the end,[6] but a judiciously chosen decreasing sequence of h values leaves very little work for this Shellsort with gaps 23, 10, 4, 1 in action
final pass to do. Class Sorting algorithm

In simplistic terms, this means if we have an array of 1024 numbers, our first gap (h) could be 512. We then Data structure Array
run through the list comparing each element in the first half to the element in the second half. Our second Worst-case O(n2) (worst known worst
gap (k) is 256, which breaks the array into four sections (starting at 0, 256, 512, 768), and we make sure the performance case gap sequence)
first items in each section are sorted relative to each other, then the second item in each section, and so on. O(n log2n) (best known
In practice the gap sequence could be anything, but the last gap is always 1 to finish the sort (effectively worst case gap
finishing with an ordinary insertion sort). sequence)[1]
Best-case O(n log n) (most gap
An example run of Shellsort with gaps 5, 3 and 1 is shown below.
performance sequences)
O(n log2n) (best known
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12
worst-case gap
Input data 62 83 18 53 07 17 95 86 47 69 25 28 sequence)[2]
After 5-sorting 17 28 18 47 07 25 83 86 53 69 62 95 Average depends on gap
After 3-sorting 17 07 18 47 28 25 69 62 53 83 86 95 performance sequence

After 1-sorting 07 17 18 25 28 47 53 62 69 83 86 95 Worst-case space О(n) total, O(1) auxiliary

complexity
The first pass, 5-sorting, performs insertion sort on five separate subarrays (a1, a6, a11), (a2, a7, a12), (a3, a8), Optimal No
(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.

Swapping pairs of items in

Pseudocode successive steps of Shellsort with
gaps 5, 3, 1
Using Marcin Ciura's gap sequence, with an inner insertion sort.

# Sort an array a[0...n-1].

gaps = [701, 301, 132, 57, 23, 10, 4, 1] # Ciura gap sequence

# 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 (gap in gaps)
{
# Do a gapped insertion sort for every element in gaps
# Each loop leaves a[0..gap-1] in gapped order
for (i = gap; i < n; i += 1)
{
# save a[i] in temp and make a hole at position i
temp = a[i]
# shift earlier gap-sorted elements up until the correct location for a[i] is found
for (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.

Author and
Worst-case
OEIS General term (k ≥ 1) Concrete gaps year of
time complexity
publication

[e.g. when
Shell, 1959[4]
N = 2p ]

Frank &
Lazarus,
1960[8]

Hibbard,
A000225
1963[9]

Papernov &
A083318 , prefixed with 1 Stasevich,
1965[10]

A003586 Successive numbers of the form (3-smooth numbers) Pratt, 1971[1]

Knuth,
1973,[3]
A003462 , not greater than
based on
Pratt, 1971[1]

Incerpi &
Sedgewick,
A036569
1985,[11]
Knuth[3]

Sedgewick,
A036562 , prefixed with 1 1982[6]

Sedgewick,
A033622
1986[12]

Gonnet &
Un­known Baeza-Yates,
1991[13]
Tokuda,
A108870 (or equivalently, ) Un­known 1992[14]
(misquote
per OEIS)

Ciura,
A102549 Unknown (experimentally derived) Un­known
2001[15]

A366726 Un­known Lee, 2021[16]

Skean,
Ehrenborg,
Un­known Jaromczyk,
2023[17]

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.[13]
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.[18] 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 < 10%.

With respect to the average number of comparisons, Ciura's sequence[15] has the best known performance; gaps greater than 701 were not determined but
the sequence can be further extended according to the recursive formula .
Tokuda's sequence, defined by the simple formula , where , , 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.[19][20]

Computational complexity
The following property holds: after h2-sorting of any h1-sorted array, the array remains h1-sorted.[21] Every h1-sorted and h2-sorted array is also
(a1h1+a2h2)-sorted, for any nonnegative integers a1 and a2. The worst-case complexity of Shellsort is therefore connected with the Frobenius problem: for
given integers h1,..., hn with gcd = 1, the Frobenius number g(h1,..., hn) is the greatest integer that cannot be represented as a1h1+ ... +anhn with
nonnegative integer a1,..., an. Using known formulae for Frobenius numbers, we can determine the worst-case complexity of Shellsort for several classes of
gap sequences.[22] Proven results are shown in the above table.

Mark Allen Weiss proved that Shellsort runs in O(N log N) time when the input array is in reverse order.[23]

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 .[24] Knuth determined the average complexity of sorting an N-element array

with two gaps (h, 1) to be .[3] It follows that a two-pass Shellsort with h = Θ(N1/3) makes on average O(N5/3)
comparisons/inversions/running time. Yao found the average complexity of a three-pass Shellsort.[25] His result was refined by Janson and Knuth:[26] the

average number of comparisons/inversions/running time made during a Shellsort with three gaps (ch, cg, 1), where h and g are coprime, is

in the first pass, in the second pass and in

the third pass. ψ(h, g) in the last formula is a complicated function asymptotically equal to . In particular,

when h = Θ(N7/15) and g = Θ(N1/5), the average time of sorting is O(N23/15).

Based on experiments, it is conjectured that Shellsort with Hibbard's gap sequence runs in O(N5/4) average time,[3] and that Gonnet and Baeza-Yates's
sequence requires on average 0.41N ln N (ln ln N + 1/6) element moves.[13] 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 .

Applying the theory of Kolmogorov complexity, Jiang, Li, and Vitányi [27] proved the following lower bound for the order of the average number of
operations/running time in a p-pass Shellsort: Ω(pN1+1/p) when p ≤ log2N and Ω(pN) when p > log2N. 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[28] for every number of passes to where . This result implies for example the

Jiang-Li-Vitányi lower bound for all -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 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 for the increment
sequence . The lower bound becomes

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

.[29][30] Robert Cypher proved a stronger lower bound: when for all .[31]

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.[32] For similar reasons, in the past, Shellsort was used in the Linux kernel.[33]

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.[34]

See also
Comb sort

References
1. Pratt, Vaughan Ronald (1979). Shellsort and Sorting Networks 15. Ciura, Marcin (2001). "Best Increments for the Average Case of
(Outstanding Dissertations in the Computer Sciences) (https://apps.dtic. Shellsort" (https://web.archive.org/web/20180923235211/http://sun.aei.p
mil/sti/pdfs/AD0740110.pdf) (PDF). Garland. ISBN 978-0-8240-4406-0. olsl.pl/~mciura/publikacje/shellsort.pdf) (PDF). In Freiwalds, Rusins
Archived (https://web.archive.org/web/20210907132436/https://apps.dti (ed.). Proceedings of the 13th International Symposium on
c.mil/sti/pdfs/AD0740110.pdf) (PDF) from the original on 7 September Fundamentals of Computation Theory. London: Springer-Verlag.
2021. pp. 106–117. ISBN 978-3-540-42487-1. Archived from the original (htt
2. "Shellsort & Comparisons" (https://web.archive.org/web/201912200405 p://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf) (PDF) on 23
46/https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html). Archived September 2018.
from the original (http://www.cs.wcupa.edu/rkline/ds/shell-comparison.ht 16. Lee, Ying Wai (21 December 2021). "Empirically Improved Tokuda Gap
ml) on 20 December 2019. Retrieved 14 November 2015. Sequence in Shellsort". arXiv:2112.11112 (https://arxiv.org/abs/2112.111
3. Knuth, Donald E. (1997). "Shell's method". The Art of Computer 12) [cs.DS (https://arxiv.org/archive/cs.DS)].
Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, 17. Skean, Oscar; Ehrenborg, Richard; Jaromczyk, Jerzy W. (1 January
Massachusetts: Addison-Wesley. pp. 83–95. ISBN 978-0-201-89685-5. 2023). "Optimization Perspectives on Shellsort". arXiv:2301.00316 (http
4. Shell, D. L. (1959). "A High-Speed Sorting Procedure" (https://web.archi s://arxiv.org/abs/2301.00316) [cs.DS (https://arxiv.org/archive/cs.DS)].
ve.org/web/20170830020037/http://penguin.ewu.edu/cscd300/Topic/Adv 18. Sedgewick, Robert (1998). "Shellsort". Algorithms in C++, Parts 1–4:
Sorting/p30-shell.pdf) (PDF). Communications of the ACM. 2 (7): 30–32. Fundamentals, Data Structure, Sorting, Searching. Reading,
doi:10.1145/368370.368387 (https://doi.org/10.1145%2F368370.36838 Massachusetts: Addison-Wesley. pp. 285–292. ISBN 978-0-201-35088-
7). S2CID 28572656 (https://api.semanticscholar.org/CorpusID:2857265 3.
6). Archived from the original (http://penguin.ewu.edu/cscd300/Topic/Ad 19. Forshell, Olof (22 May 2018). "How to choose the lengths of my sub
vSorting/p30-shell.pdf) (PDF) on 30 August 2017. Retrieved 18 October sequences for a shell sort?" (https://stackoverflow.com/a/50470237).
2011. Stack Overflow. Additional commentary at Fastest gap sequence for
5. Some older textbooks and references call this the "Shell–Metzner" sort shell sort? (https://stackoverflow.com/a/50490873#50490873) (23 May
after Marlene Metzner Norton, but according to Metzner, "I had nothing 2018).
to do with the sort, and my name should never have been attached to 20. Lee, Ying Wai (21 December 2021). "Optimal Gap Sequences in
it." See "Shell sort" (https://xlinux.nist.gov/dads/HTML/shellsort.html). Shellsort for n ≤ 16 Elements". arXiv:2112.11127 (https://arxiv.org/abs/2
National Institute of Standards and Technology. Retrieved 17 July 2007. 112.11127) [math.CO (https://arxiv.org/archive/math.CO)].
6. Sedgewick, Robert (1998). Algorithms in C (https://archive.org/details/al 21. Gale, David; Karp, Richard M. (April 1972). "A Phenomenon in the
gorithmsinc00sedg/page/273). Vol. 1 (3rd ed.). Addison-Wesley. Theory of Sorting" (https://core.ac.uk/download/pdf/82277625.pdf)
pp. 273–281 (https://archive.org/details/algorithmsinc00sedg/page/273). (PDF). Journal of Computer and System Sciences. 6 (2): 103–115.
ISBN 978-0-201-31452-6. doi:10.1016/S0022-0000(72)80016-3 (https://doi.org/10.1016%2FS0022
7. Kernighan, Brian W.; Ritchie, Dennis M. (1996). The C Programming -0000%2872%2980016-3).
Language (2nd ed.). Prentice Hall. p. 62. ISBN 978-7-302-02412-5. 22. Selmer, Ernst S. (March 1989). "On Shellsort and the Frobenius
8. Frank, R. M.; Lazarus, R. B. (1960). "A High-Speed Sorting Procedure" Problem" (https://bora.uib.no/bora-xmlui/bitstream/handle/1956/19572/O
(https://doi.org/10.1145%2F366947.366957). Communications of the n%20Shellsort%20and%20the%20Frobenius%20problem.pdf) (PDF).
ACM. 3 (1): 20–22. doi:10.1145/366947.366957 (https://doi.org/10.114 BIT Numerical Mathematics. 29 (1): 37–40. doi:10.1007/BF01932703 (h
5%2F366947.366957). S2CID 34066017 (https://api.semanticscholar.or ttps://doi.org/10.1007%2FBF01932703). hdl:1956/19572 (https://hdl.han
g/CorpusID:34066017). dle.net/1956%2F19572). S2CID 32467267 (https://api.semanticscholar.
9. Hibbard, Thomas N. (1963). "An Empirical Study of Minimal Storage org/CorpusID:32467267).
Sorting" (https://doi.org/10.1145%2F366552.366557). Communications 23. Weiss, Mark Allen (1989). "A good case for Shellsort". Congressus
of the ACM. 6 (5): 206–213. doi:10.1145/366552.366557 (https://doi.org/ Numerantium. 73: 59–62.
10.1145%2F366552.366557). S2CID 12146844 (https://api.semanticsch 24. Espelid, Terje O. (December 1973). "Analysis of a Shellsort Algorithm".
olar.org/CorpusID:12146844). BIT Numerical Mathematics. 13 (4): 394–400. doi:10.1007/BF01933401
10. Papernov, A. A.; Stasevich, G. V. (1965). "A Method of Information (https://doi.org/10.1007%2FBF01933401). S2CID 119443598 (https://ap
Sorting in Computer Memories" (https://www.mathnet.ru/links/83f0a81df i.semanticscholar.org/CorpusID:119443598). The quoted result is
1ec06f76d3683c6cab7d143/ppi751.pdf) (PDF). Problems of Information equation (8) on p. 399.
Transmission. 1 (3): 63–75. 25. Yao, Andrew Chi-Chih (1980). "An Analysis of (h, k, 1)-Shellsort" (https://
11. Incerpi, Janet; Sedgewick, Robert (1985). "Improved Upper Bounds on web.archive.org/web/20190304043832/http://pdfs.semanticscholar.org/d
Shellsort" (https://hal.inria.fr/inria-00076291/file/RR-0267.pdf) (PDF). 569/b8a70a808c6b808ca2e25371c736ce98b14f.pdf) (PDF). Journal of
Journal of Computer and System Sciences. 31 (2): 210–224. Algorithms. 1 (1): 14–50. doi:10.1016/0196-6774(80)90003-6 (https://do
doi:10.1016/0022-0000(85)90042-x (https://doi.org/10.1016%2F0022-00 i.org/10.1016%2F0196-6774%2880%2990003-6). S2CID 3054966 (http
00%2885%2990042-x). s://api.semanticscholar.org/CorpusID:3054966). STAN-CS-79-726.
12. Sedgewick, Robert (1986). "A New Upper Bound for Shellsort". Journal Archived from the original (http://pdfs.semanticscholar.org/d569/b8a70a
of Algorithms. 7 (2): 159–173. doi:10.1016/0196-6774(86)90001-5 (http 808c6b808ca2e25371c736ce98b14f.pdf) (PDF) on 4 March 2019.
s://doi.org/10.1016%2F0196-6774%2886%2990001-5). 26. Janson, Svante; Knuth, Donald E. (1997). "Shellsort with Three
13. Gonnet, Gaston H.; Baeza-Yates, Ricardo (1991). "Shellsort". Handbook Increments" (http://www2.math.uu.se/~svante/papers/sj113.pdf) (PDF).
of Algorithms and Data Structures: In Pascal and C (2nd ed.). Reading, Random Structures and Algorithms. 10 (1–2): 125–142.
Massachusetts: Addison-Wesley. pp. 161–163. ISBN 978-0-201-41607- arXiv:cs/9608105 (https://arxiv.org/abs/cs/9608105).
7. "Extensive experiments indicate that the sequence defined by CiteSeerX 10.1.1.54.9911 (https://citeseerx.ist.psu.edu/viewdoc/summar
α = 0.45454 < 5/11 performs significantly better than other sequences. y?doi=10.1.1.54.9911). doi:10.1002/(SICI)1098-
The easiest way to compute ⌊0.45454n⌋ is by (5 * n — 1)/11 using 2418(199701/03)10:1/2<125::AID-RSA6>3.0.CO;2-X (https://doi.org/10.
integer arithmetic." 1002%2F%28SICI%291098-2418%28199701%2F03%2910%3A1%2F
2%3C125%3A%3AAID-RSA6%3E3.0.CO%3B2-X).
14. Tokuda, Naoyuki (1992). "An Improved Shellsort". In van Leeuven, Jan
(ed.). Proceedings of the IFIP 12th World Computer Congress on 27. Jiang, Tao; Li, Ming; Vitányi, Paul (September 2000). "A Lower Bound
Algorithms, Software, Architecture. Amsterdam: North-Holland on the Average-Case Complexity of Shellsort" (https://homepages.cwi.n
Publishing Co. pp. 449–457. ISBN 978-0-444-89747-3. l/~paulv/papers/shellsort.pdf) (PDF). Journal of the ACM. 47 (5): 905–
911. arXiv:cs/9906008 (https://arxiv.org/abs/cs/9906008).
CiteSeerX 10.1.1.6.6508 (https://citeseerx.ist.psu.edu/viewdoc/summar
y?doi=10.1.1.6.6508). doi:10.1145/355483.355488 (https://doi.org/10.11
45%2F355483.355488). S2CID 3265123 (https://api.semanticscholar.or
g/CorpusID:3265123).
28. Vitányi, Paul (March 2018). "On the average-case complexity of 30. Plaxton, C. Greg; Suel, Torsten (May 1997). "Lower Bounds for
Shellsort" (https://homepages.cwi.nl/~paulv/papers/shell2015.pdf) Shellsort" (http://engineering.nyu.edu/~suel/papers/shell2.pdf) (PDF).
(PDF). Random Structures and Algorithms. 52 (2): 354–363. Journal of Algorithms. 23 (2): 221–240. CiteSeerX 10.1.1.460.2429 (http
arXiv:1501.06461 (https://arxiv.org/abs/1501.06461). s://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.460.2429).
doi:10.1002/rsa.20737 (https://doi.org/10.1002%2Frsa.20737). doi:10.1006/jagm.1996.0825 (https://doi.org/10.1006%2Fjagm.1996.082
S2CID 6833808 (https://api.semanticscholar.org/CorpusID:6833808). 5).
29. Plaxton, C. Greg; Poonen, Bjorn; Suel, Torsten (24–27 October 1992). 31. Cypher, Robert (1993). "A Lower Bound on the Size of Shellsort Sorting
"Improved lower bounds for Shellsort" (http://engineering.nyu.edu/~suel/ Networks". SIAM Journal on Computing. 22: 62–71.
papers/shell.pdf) (PDF). Proceedings., 33rd Annual Symposium on doi:10.1137/0222006 (https://doi.org/10.1137%2F0222006).
Foundations of Computer Science. Vol. 33. Pittsburgh, United States. 32. Novoa, Manuel III. "libc/stdlib/stdlib.c" (http://git.uclibc.org/uClibc/tree/lib
pp. 226–235. CiteSeerX 10.1.1.43.1393 (https://citeseerx.ist.psu.edu/vie c/stdlib/stdlib.c#n700). Retrieved 29 October 2014.
wdoc/summary?doi=10.1.1.43.1393). doi:10.1109/SFCS.1992.267769 33. "kernel/groups.c" (https://github.com/torvalds/linux/blob/72932611b4b05
(https://doi.org/10.1109%2FSFCS.1992.267769). ISBN 978-0-8186- bbd89fafa369d564ac8e449809b/kernel/groups.c#L105). GitHub.
2900-6. S2CID 15095863 (https://api.semanticscholar.org/CorpusID:150 Retrieved 5 May 2012.
95863).
34. Julian Seward. "bzip2/blocksort.c" (https://www.ncbi.nlm.nih.gov/IEB/To
olBox/CPP_DOC/lxr/source/src/util/compress/bzip2/blocksort.c#L519).
Retrieved 30 March 2011.

Bibliography
Knuth, Donald E. (1997). "Shell's method". The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts:
Addison-Wesley. pp. 83–95. ISBN 978-0-201-89685-5.
Analysis of Shellsort and Related Algorithms (http://www.cs.princeton.edu/~rs/shell/), Robert Sedgewick, Fourth European Symposium on Algorithms,
Barcelona, September 1996.

External links
Animated Sorting Algorithms: Shell Sort (https://web.archive.org/web/20150310043846/http://www.sorting-algorithms.com/shell-sort) at the Wayback
Machine (archived 10 March 2015) – graphical demonstration
Shellsort with gaps 5, 3, 1 as a Hungarian folk dance (https://www.youtube.com/watch?v=CmPA7zE8mx0)

Retrieved from "https://en.wikipedia.org/w/index.php?title=Shellsort&oldid=1270461617"