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 "ShellMetzner" 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 hsorted. If the file is then ksorted for some other integer k, then the file remains hsorted.^{[3]} For instance, if a list was 5sorted and then 3sorted, the list is now not only 3sorted, but both 5 and 3sorted. 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 ▸
