Shellsort

From Wikipedia, the free encyclopedia

  (Redirected from Shell Sort)

Shellsort

Shellsort with gaps 23, 10, 4, 1 in action.
Class	Sorting algorithm
Data structure	Array
Worst case performance	depends on gap sequence
Best case performance	O(N)
Average case performance	depends on gap sequence
Worst case space complexity	O(1)

Shellsort, also known as Shell sort or Shell's method is an in-place comparison sort. It generalizes an exchanging sort, such as insertion or bubble sort, by allowing the comparison and exchange of elements that lie far apart.^{[citation needed]} Its first version was published by Donald Shell in 1959.^[1][2] The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.

[edit] Description

Shellsort is a multi-pass algorithm. Each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment). This is referred to as h-sorting.
An example run of Shellsort with gaps 5, 3 and 1 is shown below.