(algorithm)
Definition: An in-place sort algorithm that repeatedly reorders different pairs of items. On each pass swap pairs of items separated by the increment or gap, if needed, and reduce the gap (divide it by about 1.3). The gap starts at about 3/4 of the number of items. Continue until the gap is 1 and a pass had no swaps.
Generalization (I am a kind of ...)
diminishing increment sort.
See also bubble sort, Shell sort.
Note: Bubble sort can be seen as a variant of comb sort where the gap is always 1. Since items may move large distances at first, comb sort 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. J. Incerpi and R. Sedgewick (1985) point out that bidirectional "bubbling" (ala bidirectional bubble sort) is more symmetric than the typical comb sort.
Author: PEB
W. Dobosiewicz, An efficient variation of bubble sort, Information Processing letters 11(1):5-6, 1980.
Richard Box and Stephen Lacey, A fast, easy sort, Byte, 16(4):315-ff, April 1991.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 24 August 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "comb sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 August 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/combSort.html