Shell sort

related topics
{math, number, function}
{@card@, make, design}
{rate, high, increase}

Shell sort is a sorting algorithm, devised by Donald Shell in 1959, that is a generalization of insertion sort, which exploits the fact that insertion sort works efficiently on input that is already almost sorted. It improves on insertion sort by allowing the comparison and exchange of elements that are far apart. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.

The algorithm is an example of an algorithm that is simple to code but difficult to analyze theoretically.

Contents

History

The Shell sort is named after its inventor, Donald Shell, who published the algorithm in 1959.[1] Some older textbooks and references call this the "Shell-Metzner" sort after Marlene Metzner Norton, but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it."[2]

Description

The principle of Shell sort is to rearrange the file so that looking at every hth element yields a sorted file. We call such a file h-sorted. If the file is then k-sorted for some other integer k, then the file remains h-sorted.[3] For instance, if a list was 5-sorted and then 3-sorted, the list is now not only 3-sorted, but both 5- and 3-sorted. If this were not true, the algorithm would undo work that it had done in previous iterations, and would not achieve such a low running time.

The algorithm draws upon a sequence of positive integers known as the increment sequence. Any sequence will do, as long as it ends with 1, but some sequences perform better than others.[4] The algorithm begins by performing a gap insertion sort, with the gap being the first number in the increment sequence. It continues to perform a gap insertion sort for each number in the sequence, until it finishes with a gap of 1. When the increment reaches 1, the gap insertion sort is simply an ordinary insertion sort, guaranteeing that the final list is sorted. Beginning with large increments allows elements in the file to move quickly towards their final positions, and makes it easier to subsequently sort for smaller increments.[3]

Although sorting algorithms exist that are more efficient, Shell sort remains a good choice for moderately large files because it has good running time and is easy to code.

Shell sort algorithm in pseudocode

The following is an implementation of Shell sort written in pseudocode. The increment sequence is a geometric sequence in which every term is roughly 2.2 times smaller than the previous one:

Full article ▸

related documents
Brouwer fixed point theorem
Tree automaton
Naive Bayes classifier
Root-finding algorithm
Symmetric matrix
Analytic function
Pell's equation
Tangent space
Selection sort
Fundamental theorem of arithmetic
Delaunay triangulation
Uniform convergence
Scientific notation
Orthogonality
Embedding
Octonion
Burnside's problem
Befunge
MathML
Sufficiency (statistics)
Curve
Analytic continuation
Total order
Binomial theorem
Tensor
Finite state machine
Affine transformation
Knapsack problem
Polish notation
Greatest common divisor