EDIT: The Wikipedia article mentioned here was incorrect and has since been updated.  Comb sort's worst-case behavior is $\Omega(n^2)$, not $O(n \log n)$ as was claimed.Yesterday I stumbled on the comb sort algorithm, a modification of bubble sort similar in spirit to Shell sort.  The idea is to maintain a gap of some size, then use a bubble-sort pass over the array using that gap size to roughly position the elements into their proper positions.  Each iteration decreases the gap size, until eventually the algorithm degrades into bubble sort.The Wikipedia article claims that the algorithm runs in O(n log n) time worst-case, but the citation for this claim is a paper on GPU processing that mentions this result offhand without providing any analysis or citation.  One of the original papers on comb sort doesn't even attempt to prove a worst-case bound, and in fact not a single source I've found has attempted to analyze the worst-case or even average-case complexity of comb sort.  This concerns me, since I've found a lot of sites that are clearly getting their information from the Wikipedia article, and I would hate for a single bad source to propagate the O(n log n) claim if it is incorrect.My question is this: is there a reliable source that proves the O(n log n) worst-case behavior of comb sort?Thanks!
Analysis of Comb Sort?
ds.algorithms;reference request
The $\Omega(n^2)$ worst-case lower bound of Comb sort (or Dobosiewicz sort) has also been proved using the incompressibility method based on Kolmogorov complexity. See for example the survey by Vitanyi, page 16. If you are also interested in the average-case lower bound on the running time, the paper gives that as well. Moreover the proofs obtained with the method are natural, easy-to-follow and usually quite short.