Difference between revisions 11669888 and 11761130 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.  
It is easy to develop an intuitive sense of how this algorithm works, but often difficult to analyze its execution time.

Shell sort is sometimes called "Shell-Metzner" sort" after Marlene Metzner who wrote a very early implementation of Shell sort in [[FORTRAN]].  It was first called Shell-Metzner in an article in ''Creative Computing'' in [[1976]], but Marlene Metzner has said that her name should never have been attached to it.

== Basic concept ==

Shell sort is really just an extension of [[insertion sort]], with two observations in mind: 
#Insertion sort is efficient if the input is almost sorted. 
#Insertion sort is inefficient, on average, because it moves values just one position at a time. 

Shell sort is similar to insertion sort, but it works by taking bigger steps as it rearranges values, gradually decreasing the step size down towards one. 
In the end, Shell sort performs a regular insertion sort, but by then, the array of data is guaranteed to be almost sorted. 

(contracted; show full)
[[de:Shellsort]]
[[es:Ordenación Shell]]
[[lt:Kevalo r&#363;&#353;iavimo algoritmas]]
[[nl:Shellsort]]
[[ja:&#12471;&#12455;&#12523;&#12477;&#12540;&#12488;]]
[[zh:&#24076;&#23572;&#25490;&#24207;]]
[[Category:Sort algorithms]]