ShellSort was invented by Donald Shell in 1959 and was O(N^2) as introduced.
The algorithm makes multiple passes through the list, and each time sorts a number of equally sized sets using the insertion sort. The size of the set to be sorted gets larger with each pass through the list, until the set consists of the entire list.
The items contained in each set are not contiguous - rather, if there are
i sets then a set is composed of every
i-th element. For example, if there are 3 sets then the first set would contain the elements located at positions 1, 4, 7 and so on. The second set would contain the elements located at positions 2, 5, 8, and so on; while the third set would contain the items located at positions 3, 6, 9, and so on. Donald Shell originally suggested N/2 sets, such that every set had a fixed number of elements and one would increment the index by a fixed count of N/2 positions to reach the next element. Improved forms of
ShellSort use geometric progressions for increments rather than fixed sets ('incremental' improvements? :-) in order to achieve better worst-case performance. An increment of 2^k gets you O(N^(3/2)), for example. Papers published in 1979 and 1992 describe increment mechanisms to improve this to O(N log^2 N) and O(N log N) respectively, though neither of these allow
ShellSort to beat
QuickSort (1961) for coefficient speed.
See the
WikiPedia entry (
http://en.wikipedia.org/wiki/Shell_sort) for more detailed illustrations.
See
http://linux.wku.edu/~lamonml/algor/sort/shell.html, from which the above may have been taken.