Difference between revisions 7885294 and 8124235 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)
But since data are presorted by the preceding steps (''h'' = 3, 7, 21, ...), only a few insertion sort steps are sufficient. 
The exact number depends on the sequence of ''h'' values (denoted as ''h''-sequence). The ''h''-sequence above is just one of several possible.


([[Vaughan Pratt|Pratt]])With the ''h''-sequence 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2<sup>''p''</sup>3<sup>''q''</sup>, ... Shellsort needs O(''n''·log(''n'')<sup>2</sup>) steps for sorting a sequence of length ''n''.

(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]]