
Shellsort
A sorting algorithm that generalizes insertion sort by comparing elements far apart, with a gap that shrinks step by step.
- Year
- 1959
- People involved
- Donald Shell
- Section
- Computing
History
Shellsort is an algorithm for putting a list of items in order, from smallest to largest. Its importance lies in solving, much faster than simple methods, a problem that otherwise demands a huge number of comparisons when the list is long. Its central idea is to first arrange elements that lie far apart, so that badly placed values can jump large distances toward their correct positions.
Before Shell, the common methods were bubble sort and insertion sort. Insertion sort works very well when a list is nearly sorted, but in general it is slow, because each item moves only one position at a time. If a small value sits at the end of a long list, it may need almost as many steps as there are items to reach the front. Donald Shell noticed that if elements separated by a gap of several positions are compared and sorted first, values move far more quickly.
The method works in passes. In each pass a gap is chosen, and the subsets formed by elements separated by that gap are sorted with insertion sort. One can picture writing the list into a table with as many columns as the gap, sorting each column, and reading the table back as a single list. The process then repeats with a smaller gap. The final gap is 1, which is an ordinary insertion sort, but by then the list is nearly ordered, so that last pass is cheap. The key property is that earlier passes are not undone: a list sorted with gap 5 stays sorted within each gap-5 subset even after it is sorted with gap 3.
Shell published the method in 1959. The gap sequence he proposed started at half the list length and was halved until reaching 1. That choice greatly improved on quadratic methods, but it was later found that in certain cases it could still be slow, with a worst-case running time of order n squared. Over the following years other gap sequences were proposed. Vaughan Pratt showed that a small variation brings the worst case down to order n log squared n, at the cost of a more complicated method. Robert Sedgewick and others proposed sequences that perform better in practice, and Marcin Ciura found by experiment a sequence that works well for lists of moderate size.
The theoretical analysis of the method proved very difficult, and open questions remain, including whether some variant can reach the optimal worst-case time of the best comparison sorts. Even so, its simplicity made it popular for decades, especially on systems with limited memory, since it sorts within the same array without needing significant extra space. Today standard libraries usually rely on faster general-purpose algorithms, such as variants of quicksort or merge sort, but Shellsort is still taught as an example of how a simple idea, comparing distant elements, can turn a slow method into a reasonably efficient one.
Timeline
- 1959Donald Shell publishes the method, which bears his name.
- 1959Shell proposes a gap sequence that starts at half the list size and is halved each time.
- 1971Vaughan Pratt shows that a small variation reduces the worst case to order n log squared n.
- 1986Robert Sedgewick proposes gap sequences that improve practical performance.
- 2001Marcin Ciura publishes a gap sequence found by experiment, with good results on lists of moderate size.
Trivia and anecdotes
Nothing to do with shells
Despite its name, the method has nothing to do with shells; the name comes from its inventor's surname.
A disputed name
Some older texts call it Shell-Metzner after Marlene Metzner Norton, but she stated she had nothing to do with the algorithm and that her name should not be attached to it.