Difference between revisions 8419559 and 8419593 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)
([[Insertion sort]]) The worst case of Shell sort is the basic insertion sort (using a single ''h''-step of 1), which requires O(''n''&sup2;) comparisons and exchanges.

An easily computable ''h''-sequence for Shell sort is the [[Fibonacci number|Fibonacci Sequence]] (1, 2, 3, 5, 8, 13, 21, ... ), which increases step size in a natural progression.

== Implementations ==


'''The following''' [[Java_programming_language|Java]] program sorts an array ''a'' from index ⏎
== position 0 through ==
<math>15+23</math>
== Headline text ==

== Headline text ==⏎
 ''n''-1. The number of columns used for arranging data in each step is in array ''cols''. Thus, data are arranged in 1,391,376 columns in the first step and in one column in the last step. Note that essentially nothing is done if the number of columns ''h'' is larger than the number of data elements ''n''. Each column is sorted by insertion sort. First, data of the second row, beginning at ''i'' = '(contracted; show full)* [http://www.nist.gov/dads/HTML/shellsort.html Dictionary of Algorithms and Data Structures: Shellsort]

[[de:Shellsort]]
[[es:Ordenación Shell]]
[[nl:Shellsort]]
[[ja:&#12471;&#12455;&#12523;&#12477;&#12540;&#12488;]]

[[Category:Sort algorithms]]