Editing Comb sort (section)

{{Short description|Interval based sorting algorithm}}
{{Infobox algorithm
|class=[[Sorting algorithm]]
|image=[[File:comb_sort_demo.gif|Visualisation of comb sort]]
|caption=Comb sort with shrink factor ''k''=1.24733
|data=[[Array data structure|Array]]
|time=<math>O(n^2)</math><ref name=BB>{{Cite journal
  | doi = 10.1016/S0020-0190(00)00223-4
  | title = Analyzing variants of Shellsort
  | last1 = Brejová | first1 = Bronislava
  | journal = [[Information Processing Letters]]
  | volume = 79 | issue = 5 | pages = 223–227
  | date = 15 September 2001
}}</ref>
|average-time=<math>\Omega(n^2/2^p)</math>, where {{math|''p''}} is the number of increments<ref name=BB/>
|best-time=<math>\Theta(n \log n)</math>
|space=<math>O(1)</math>
|optimal=
}}
'''Comb sort''' is a relatively simple [[sorting algorithm]] originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980,<ref name=BB/><ref>{{Cite journal
 |title=An efficient variation of bubble sort
 |first=Wlodzimierz |last=Dobosiewicz
 |journal=Information Processing Letters
 |volume=11 |issue=1 |date=29 August 1980 |pages=5–6
 |doi=10.1016/0020-0190(80)90022-8
}}</ref> later rediscovered (and given the name "Combsort") by Stephen Lacey and Richard Box in 1991.<ref>{{cite news
 |url=http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm
 |title=A Fast, Easy Sort: A novel enhancement makes a bubble sort into one of the fastest sorting routines
 |first1=Stephen |last1=Lacey  |first2=Richard |last2=Box  |journal=[[Byte Magazine]]
 |department=Hands On  |date=April 1991
 |volume=16 |issue=4 |pages=315–318, 320
 |archive-url=https://web.archive.org/web/20210927224138/http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm
 |archive-date=2021-09-27
 |url-status=dead
}}  [https://archive.org/details/eu_BYTE-1991-04_OCR Entire magazine] available at archive.org.</ref> Comb sort improves on [[bubble sort]] in the same way that [[Shellsort]] improves on [[insertion sort]], in that they both allow elements that start far away from their intended position to move more than one space per swap.

''[[National Institute of Standards and Technology|nist.gov]]'''s "diminishing increment sort" definition mentions the term 'comb sort' as visualizing iterative passes of the data, "where the teeth of a comb touch;" the former term is linked to [[Donald Knuth|Don Knuth]].<ref>{{cite web
   |url=https://xlinux.nist.gov/dads/HTML/diminishingIncSort.html
   |title=diminishing increment sort
   |accessdate=March 9, 2021}}</ref>