Shell Sort

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.