Difference between revisions 20953942 and 22184006 on enwiki

'''Shell sort''' (or '''Shellsort''') is one of the oldest [[sorting algorithm|sorting algorithms]]. It was invented in 1959 by [[D. L. Shell|Donald L. Shell]] <nowiki>[</nowiki>[[#References|Sh]]<nowiki>]</nowiki>.
It is fast, easy to understand and easy to implement. 
However, its complexity analysis is a little more sophisticated.  
(contracted; show full)

The best known sequence of increments in terms of the average number of comparisons made is 1, 4, 10, 23, 57, 132, 301, 701 (further increments unknown) ([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A102549 A102549]) [http://www-zo.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf]. The increments were found empirically; no formula for them is known.


 * Gene Michael Stover used [[genetic algorithm]]s to evolve high-performance sequences for shell sort, outperforming Sedgewick and other sequences [http://www.cybertiggyr.com/gene/htdocs/shiva-0/shiva-0.html]. He argues that using genetic algorithms with larger population size and more generations could create even more efficient sequences.⏎
⏎
See also [http://www.research.att.com/~njas/sequences/Sindx_So.html#sorting this entry in OEIS's sequences index] for a list of sequences used in shell sorting.

== Implementations ==

=== Using a list of shell sizes ===

(contracted; show full)[[de:Shellsort]]
[[es:Ordenación Shell Sort]]
[[it:Shell sort]]
[[lt:Šelo rūšiavimo algoritmas]]
[[nl:Shellsort]]
[[ja:シェルソート]]
[[pt:Shell sort]]
[[zh:希尔排序]]