Difference between revisions 13141262 and 13141445 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 an extension of [[insertion sort]], with two observations in mind: 
#Insertion sort is efficient if the input is almost sorted. 
(contracted; show full)
[[de:Shellsort]]
[[es:Ordenación Shell Sort]]
[[it:Shell sort]]
[[lt:Kevalo r&#363;&#353;iavimo algoritmas]]
[[nl:Shellsort]]
[[ja:&#12471;&#12455;&#12523;&#12477;&#12540;&#12488;]]
[[zh:&#24076;&#23572;&#25490;&#24207;]]