Movatterモバイル変換

Shellsort

From Wikipedia, the free encyclopedia

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(n²) (worst known worst case gap sequence) O(n log²n) (best known worst case gap sequence)^[1]
Best-case performance	O(n logn) (most gap sequences) O(n log²n) (best known worst-case gap sequence)^[2]
Average performance	depends on gap sequence
Worst-case space complexity	О(n) total, O(1) auxiliary
Optimal	No

The steps of Shellsort. — Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1

Shellsort, also known asShell sort orShell's method, is anin-place comparison sort. It can be 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. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining theirtime complexity remains anopen problem.

The algorithm was first published byDonald Shell in 1959, and has nothing to do with shells.^[4]^[5]

Description

[edit]

Shellsort is an optimization ofinsertion 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 everyhth element produces a sorted list. Such a list is said to beh-sorted. It can also be thought of ash interleaved lists, each individually sorted.^[6] Beginning with large values ofh allows elements to move long distances in the original list, reducing large amounts of disorder quickly, and leaving less work for smallerh-sort steps to do.^[7] If the list is thenk-sorted for some smaller integerk, then the list remainsh-sorted. A final sort withh = 1 ensures the list is fully sorted at the end,^[6] but a judiciously chosen decreasing sequence ofh values leaves very little work for this final pass to do.

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.

	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	a₁₁	a₁₂
Input data	62	83	18	53	07	17	95	86	47	69	25	28
After 5-sorting	17	28	18	47	07	25	83	86	53	69	62	95
After 3-sorting	17	07	18	47	28	25	69	62	53	83	86	95
After 1-sorting	07	17	18	25	28	47	53	62	69	83	86	95

The first pass, 5-sorting, performs insertion sort on five separate subarrays (a₁,a₆,a₁₁), (a₂,a₇,a₁₂), (a₃,a₈), (a₄,a₉), (a₅,a₁₀). For instance, it changes the subarray (a₁,a₆,a₁₁) from (62, 17, 25) to (17, 25, 62). The next pass, 3-sorting, performs insertion sort on the three subarrays (a₁,a₄,a₇,a₁₀), (a₂,a₅,a₈,a₁₁), (a₃,a₆,a₉,a₁₂). The last pass, 1-sorting, is an ordinary insertion sort of the entire array (a₁,...,a₁₂).

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.

Unlikeinsertion sort, Shellsort is not astable sort since gapped insertions transport equal elements past one another and thus lose their original order. It is anadaptive sorting algorithm in that it executes faster when the input is partially sorted.

Example

[edit]

This is aC# example using Marcin Ciura's gap sequence, with an inner insertion sort.

usingSystem.Collections.Generic;// Sort an array a[0...n-1].List<int>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 stepforeach(intgapingaps){// Do a gapped insertion sort for every element in gaps// Each loop leaves a[0..gap-1] in gapped orderfor(inti=gap;i<n;++i){// save a[i] in temp and make a hole at position iinttemp=a[i];// shift earlier gap-sorted elements up until the correct location for a[i] is foundfor(intj=i;(j>=gap)&&(a[j-gap]>temp);j-=gap){a[j]=a[j-gap];}// put temp (the original a[i]) in its correct locationa[j]=temp;}}

Gap sequences

[edit]

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 thanN should be used in reverse order.

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 ,\left\lfloor {\frac {N}{2}}\right\rfloor$	$\Theta \left(N^{2}\right)$ [e.g. whenN = 2^p]	Shell, 1959^[4]
	$2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1$	$1,3,\ldots ,\;2\left\lfloor {\frac {N}{8}}\right\rfloor +1,\;\;2\left\lfloor {\frac {N}{4}}\right\rfloor +1$	$\Theta \left(N^{\frac {3}{2}}\right)$	Frank & Lazarus, 1960^[8]
A000225	$2^{k}-1$	$1,3,7,15,31,63,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Hibbard, 1963^[9]
A083318	$2^{k}+1$ , prefixed with 1	$1,3,5,9,17,33,65,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Papernov & Stasevich, 1965^[10]
A003586	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^[1]
A003462	${\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,^[3] based onPratt, 1971^[1]
A036569	${\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{where}}\\a_{0}={}&3\\a_{q}={}&\min \left\{n\in \mathbb {N} \colon n\geq \left({\frac {5}{2}}\right)^{q+1},\forall p\colon 0\leq p<q\Rightarrow \gcd(a_{p},n)=1\right\}\\I={}&\left\{0\leq q<r\mid q\neq {\frac {1}{2}}\left(r^{2}+r\right)-k\right\}\\r={}&\left\lfloor {\sqrt {2k+{\sqrt {2k}}}}\right\rfloor \end{aligned}}$	$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,^[11]Knuth^[3]
A036562	$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^[6]
A033622	${\begin{cases}9\left(2^{k}-2^{\frac {k}{2}}\right)+1&k{\text{ even}},\\8\cdot 2^{k}-6\cdot 2^{(k+1)/2}+1&k{\text{ odd}}\end{cases}}$	$1,5,19,41,109,\ldots$	$O\left(N^{\frac {4}{3}}\right)$	Sedgewick, 1986^[12]
	$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 ,\left\lfloor {\frac {5N-1}{11}}\right\rfloor$	Unknown	Gonnet &Baeza-Yates, 1991^[13]
A108870	$\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$	Unknown	Tokuda, 1992^[14] (misquote per OEIS)
A102549	Unknown (experimentally derived)	$1,4,10,23,57,132,301,701$	Unknown	Ciura, 2001^[15]
A366726	$\left\lceil {\frac {\gamma ^{k}-1}{\gamma -1}}\right\rceil ,\gamma =2.243609061420001\ldots$	$1,4,9,20,45,102,230,516,\ldots$	Unknown	Lee, 2021^[16]
	$\left\lfloor 4.0816\cdot 8.5714^{\frac {k}{2.2449}}\right\rfloor$	$1,4,10,27,72,187,488,\ldots$	Unknown	Skean, Ehrenborg, Jaromczyk, 2023^[17]

When the binary representation ofN contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(N²) comparisons in the worst case. For instance, this case occurs forN 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 theO(N log N) that is optimal for comparison sorts, Pratt's version lends itself tosorting networks and has the same asymptotic gate complexity as Batcher'sbitonic 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 lowgreatest common divisors or are pairwisecoprime.^[18]^{[failed verification]}

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 $h_{k}=\lfloor 2.25h_{k-1}\rfloor$ .

Tokuda's sequence, defined by the simple formula $h_{k}=\lceil h'_{k}\rceil$ , where $h'_{k}=2.25h'_{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 asquicksort ormerge sort, then it is possible to tabulate an optimal sequence for each input size.^[19]^[20] For N = 128 and N = 1000, Ciura found that (1, 4, 9, 24, 85) and (1, 4, 10, 23, 57, 156, 409, 995) made the fewest number of comparisons on average respectively.^[15]

Computational complexity

[edit]

The following property holds: afterh₂-sorting of anyh₁-sorted array, the array remainsh₁-sorted.^[21] Everyh₁-sorted andh₂-sorted array is also (a₁h₁+a₂h₂)-sorted, for any nonnegative integersa₁ anda₂. The worst-case complexity of Shellsort is therefore connected with theFrobenius problem: for given integersh₁,...,h_n with gcd = 1, the Frobenius numberg(h₁,...,h_n) is the greatest integer that cannot be represented asa₁h₁+ ... +a_nh_n with nonnegative integera₁,...,a_n. 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 inO(N logN) 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 $0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)$ .^[24]Knuth determined the average complexity of sorting anN-element array with two gaps (h, 1) to be ${\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}$ .^[3] It follows that a two-pass Shellsort withh = Θ(N^1/3) makes on averageO(N^5/3) comparisons/inversions/running time.Yao found the average complexity of a three-pass Shellsort.^[25] His result was refined byJanson and Knuth:^[26] the average number of comparisons/inversions/running time made during a Shellsort with three gaps (ch,cg, 1), whereh andg are coprime, is ${\frac {N^{2}}{4ch}}+O(N)$ in the first pass, ${\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)$ in the second pass and $\psi (h,g)N+{\frac {1}{8}}{\sqrt {\frac {\pi }{c}}}(c-1)N^{3/2}+O\left((c-1)gh^{1/2}N\right)+O\left(c^{2}g^{3}h^{2}\right)$ in the third pass.ψ(h,g) in the last formula is a complicated function asymptotically equal to ${\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+O\left(gh^{-1/2}\right)$ . In particular, whenh = Θ(N^7/15) andg = Θ(N^1/5), the average time of sorting isO(N^23/15).

Based on experiments, it is conjectured that Shellsort withHibbard's gap sequence runs inO(N^5/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 thetheoretical lower bound, i.e. log₂N!. Ciuria's sequence 1, 4, 10, 23, 57, 132, 301, 701 (labelled Ci01) has been extended according to the formula $h_{k}=\lfloor 2.25h_{k-1}\rfloor$ .

Applying the theory ofKolmogorov complexity, Jiang,Li, andVitányi^[27] proved the following lower bound for the order of the average number of operations/running time in ap-pass Shellsort: Ω(pN^1+1/p) whenp ≤ log₂N and Ω(pN) whenp > log₂N.Therefore, Shellsort has prospects of running in an average time that asymptotically grows likeN 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 byVitányi^[28] for every number of passes $p {\displaystyle p}$ to $\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 {\displaystyle 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, andSuel showed that it grows at least as rapidly as $\Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)$ .^[29]^[30]Robert Cypher proved a stronger lower bound: $\Omega \left(N{{(\log N)^{2}} \over {\log \log N}}\right)$ when $h_{s+1}>h_{s}$ for all $s {\displaystyle s}$ .^[31]

Applications

[edit]

Shellsort performs more operations and has highercache miss ratio thanquicksort. However, since it can be implemented using little code and does not use thecall stack, some implementations of theqsort function in theC standard library targeted atembedded systems use it instead of quicksort. Shellsort is, for example, used in theuClibc library.^[32] For similar reasons, in the past, Shellsort was used in theLinux kernel.^[33]

Shellsort can also serve as a sub-algorithm ofintrospective 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 thebzip2 compressor.^[34]

References

[edit]

^^a ^b ^cPratt, 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 fromthe original on 20 December 2019. Retrieved14 November 2015.
^^a ^b ^c ^d ^eKnuth, 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.
^^a ^bShell, 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 fromthe original(PDF) on 30 August 2017. Retrieved18 October 2011.
^Some older textbooks and references call this the "Shell–Metzner" sort afterMarlene 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. Retrieved17 July 2007.
^^a ^b ^cSedgewick, Robert (1998).Algorithms in C. Vol. 1 (3rd ed.). Addison-Wesley. pp. 273–281.ISBN 978-0-201-31452-6.
^Kernighan, Brian W.;Ritchie, Dennis M. (1996).The C Programming Language (2nd ed.). Prentice Hall. p. 62.ISBN 978-7-302-02412-5.
^Frank, R. M.; Lazarus, R. B. (1960)."A High-Speed Sorting Procedure".Communications of the ACM.3 (1):20–22.doi:10.1145/366947.366957.S2CID 34066017.
^Hibbard, Thomas N. (1963)."An Empirical Study of Minimal Storage Sorting".Communications of the ACM.6 (5):206–213.doi:10.1145/366552.366557.S2CID 12146844.
^Papernov, A. A.; Stasevich, G. V. (1965)."A Method of Information Sorting in Computer Memories"(PDF).Problems of Information Transmission.1 (3):63–75.
^Incerpi, Janet;Sedgewick, Robert (1985)."Improved Upper Bounds on Shellsort"(PDF).Journal of Computer and System Sciences.31 (2):210–224.doi:10.1016/0022-0000(85)90042-x.
^Sedgewick, Robert (1986). "A New Upper Bound for Shellsort".Journal of Algorithms.7 (2):159–173.doi:10.1016/0196-6774(86)90001-5.
^^a ^b ^cGonnet, Gaston H.; Baeza-Yates, Ricardo (1991). "Shellsort".Handbook of Algorithms and Data Structures: In Pascal and C (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 161–163.ISBN 978-0-201-41607-7.Extensive experiments indicate that the sequence defined byα = 0.45454 < 5/11 performs significantly better than other sequences. The easiest way to compute⌊0.45454n⌋ is by(5 *n — 1)/11 using integer arithmetic.
^Tokuda, Naoyuki (1992). "An Improved Shellsort". In van Leeuven, Jan (ed.).Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture. Amsterdam: North-Holland Publishing Co. pp. 449–457.ISBN 978-0-444-89747-3.
^^a ^b ^cCiura, Marcin (2001)."Best Increments for the Average Case of Shellsort"(PDF). In Freiwalds, Rusins (ed.).Proceedings of the 13th International Symposium on Fundamentals of Computation Theory. London: Springer-Verlag. pp. 106–117.ISBN 978-3-540-42487-1. Archived fromthe original(PDF) on 23 September 2018.
^Lee, Ying Wai (21 December 2021). "Empirically Improved Tokuda Gap Sequence in Shellsort".arXiv:2112.11112 [cs.DS].
^Skean, Oscar; Ehrenborg, Richard; Jaromczyk, Jerzy W. (1 January 2023). "Optimization Perspectives on Shellsort".arXiv:2301.00316 [cs.DS].
^Sedgewick, Robert (1998). "Shellsort".Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching. Reading, Massachusetts: Addison-Wesley. pp. 285–292.ISBN 978-0-201-35088-3.
^Forshell, Olof (22 May 2018)."How to choose the lengths of my sub sequences for a shell sort?".Stack Overflow. Additional commentary atFastest gap sequence for shell sort? (23 May 2018).
^Lee, Ying Wai (21 December 2021). "Optimal Gap Sequences in Shellsort forn ≤ 16 Elements".arXiv:2112.11127 [math.CO].
^Gale, David;Karp, Richard M. (April 1972)."A Phenomenon in the Theory of Sorting"(PDF).Journal of Computer and System Sciences.6 (2):103–115.doi:10.1016/S0022-0000(72)80016-3.
^Selmer, Ernst S. (March 1989)."On Shellsort and the Frobenius Problem"(PDF).BIT Numerical Mathematics.29 (1):37–40.doi:10.1007/BF01932703.hdl:1956/19572.S2CID 32467267.
^Weiss, Mark Allen (1989). "A good case for Shellsort".Congressus Numerantium.73:59–62.
^Espelid, Terje O. (December 1973). "Analysis of a Shellsort Algorithm".BIT Numerical Mathematics.13 (4):394–400.doi:10.1007/BF01933401.S2CID 119443598. The quoted result is equation (8) on p. 399.
^Yao, Andrew Chi-Chih (1980)."An Analysis of (h,k, 1)-Shellsort"(PDF).Journal of Algorithms.1 (1):14–50.doi:10.1016/0196-6774(80)90003-6.S2CID 3054966. STAN-CS-79-726. Archived fromthe original(PDF) on 4 March 2019.
^Janson, Svante;Knuth, Donald E. (1997)."Shellsort with Three Increments"(PDF).Random Structures and Algorithms.10 (1–2):125–142.arXiv:cs/9608105.CiteSeerX 10.1.1.54.9911.doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<125::AID-RSA6>3.0.CO;2-X.
^Jiang, Tao;Li, Ming;Vitányi, Paul (September 2000)."A Lower Bound on the Average-Case Complexity of Shellsort"(PDF).Journal of the ACM.47 (5):905–911.arXiv:cs/9906008.CiteSeerX 10.1.1.6.6508.doi:10.1145/355483.355488.S2CID 3265123.
^Vitányi, Paul (March 2018)."On the average-case complexity of Shellsort"(PDF).Random Structures and Algorithms.52 (2):354–363.arXiv:1501.06461.doi:10.1002/rsa.20737.S2CID 6833808.
^Plaxton, C. Greg;Poonen, Bjorn;Suel, Torsten (24–27 October 1992)."Improved lower bounds for Shellsort"(PDF).Proceedings., 33rd Annual Symposium on Foundations of Computer Science. Vol. 33. Pittsburgh, United States. pp. 226–235.CiteSeerX 10.1.1.43.1393.doi:10.1109/SFCS.1992.267769.ISBN 978-0-8186-2900-6.S2CID 15095863.{{cite book}}: CS1 maint: location missing publisher (link)
^Plaxton, C. Greg;Suel, Torsten (May 1997)."Lower Bounds for Shellsort"(PDF).Journal of Algorithms.23 (2):221–240.CiteSeerX 10.1.1.460.2429.doi:10.1006/jagm.1996.0825.
^Cypher, Robert (1993). "A Lower Bound on the Size of Shellsort Sorting Networks".SIAM Journal on Computing.22:62–71.doi:10.1137/0222006.
^Novoa, Manuel III."libc/stdlib/stdlib.c". Retrieved29 October 2014.
^"kernel/groups.c".GitHub. Retrieved5 May 2012.
^Julian Seward."bzip2/blocksort.c". Retrieved30 March 2011.

Bibliography

[edit]

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, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.

External links

[edit]

The WikibookAlgorithm implementation has a page on the topic of:Shell sort

Animated Sorting Algorithms: Shell Sort at theWayback Machine (archived 10 March 2015) – graphical demonstration
Shellsort with gaps 5, 3, 1 as a Hungarian folk dance

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Introsort Kirkpatrick–Reisch sort Merge-insertion sort Powersort Timsort Spreadsort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort
Impractical sorts	Stooge sort Slowsort Bogosort