(algorithm)
Definition: An in-place sort algorithm that repeatedly reorders different, small subsets of the input until the entire array is ordered. On each pass it handles i sets of n/i items, where n is the total number of items. Each set is every ith item, e.g. set 1 is item 1, 1+i, 1+2i, etc., set 2 is item 2, 2+i, etc. On each succeeding pass, the increment or gap, i, is reduced until it is 1 for the last pass.
Generalization (I am a kind of ...)
in-place sort.
Specialization (... is a kind of me.)
Shell sort, comb sort.
Note: Since items may move large distances at first, this method is quite efficient. Comb sort does a single "bubbling" pass (ala bubble sort) over each set for each gap or increment, whereas Shell sort completely sorts each set.
Shell had the first increment be half the number of items to be sorted, i.e., 
n/2
, and each succeeding increment half the preceding increment. This lowers efficiency since the same items are compared over and over. Relatively prime increments are better.
Since one of the sets can be visualized as those items where the teeth of a comb touch, this is sometimes called a comb sort. Using this analogy, the teeth get closer on each pass. However, the term "comb sort" is used for a specific algorithm. Knuth uses "diminishing increment sort" as a synonym of "Shell sort", but we include comb sort.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 7 January 2005.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black and Art S. Kagel, "diminishing increment sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 7 January 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/diminishingIncSort.html