(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 i^{th} 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.*

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 7 January 2005.

HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:

Paul E. Black and Art S. Kagel, "diminishing increment sort", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 7 January 2005. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/diminishingIncSort.html