7
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ If you pretend the gap reduces by a factor of 2 at each step, then after the first step when gap <= 2, then we are left with two sequences (odd and even) that are individually sorted. Clearly, it takes only linear time at this stage to merge them, and the time to get here is $O(n\log n)$ since each step takes at most $n$ time, and the gap starts at $n$, reducing by a constant factor at each step. $\endgroup$ – Suresh Venkat Jan 5 '12 at 22:32
  • $\begingroup$ @SureshVenkat- Comb sort doesn't work by repeatedly applying bubble sort until the elements spaced by the gap are sorted; instead it applies one pass swapping elements spaced by the gap that are out of order and then decreases the gap. As a result, I don't think you can claim that after the 2-gap pass you have two interleaved sorted sequences. Let me know if I'm wrong about this. $\endgroup$ – templatetypedef Jan 5 '12 at 22:38
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

So after some digging it looks like the original analysis in Wikipedia was incorrect. This paper cites an older paper that gives $\Omega(n^2)$ as a lower bound for comb sort, and actually says that it was still an open problem (as of the time that the paper was written) to determine whether the worst-case actually was $O(n^2)$ on all inputs. I've updated the Wikipedia article appropriately.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.