According to wikipedia, Cocktail-sort has an average performance of $O(n^2)$, whereas Comb-sort's average performance is $Ω(n^2/2^p)$, where $p$ is the number of increments.
There's no explanation given for this substantial difference between two similar algorithms, both variants of Bubble-sort. Can anyone help explain it?
Sorting is all about removing inversions.
Combsort is much faster than cock-tail sort because it does more "long range" comparisons and exchanges; exchanging two out-of-order elements that are far apart will (on average) remove (a lot more) more inversions than exchanging two that are close together.
As for the formula you quote... well, Wikipedia's wrong. Combsort isn't that much faster. The formula you quote is a (very) weak lower bound on the average number of comparisons (try substituting p=2.log2(n) into the formula. Combsort can't possibly require only O(1) comparisons to perform the whole sort because... it's obviously had to do about pn, before the insertion sort phase, at the end of the sort, even begins).
[I think that formula has been (mis)quoted on the Wikipedia Combsort page since something like 2008, and I don't think anyone bothered to point out, even on Wikipedia's Combsort talk page, that the paper being referenced gave it as a formula, only for a lower bound, before June 2013.]
In practice, unless you are sorting billions of records, if you use increments that are relatively prime and have a growth ratio of 1.25 or so, Combsort will require (on average) about 3*log2(n)*n comparisons (and will generally run somewhere between 2 and 3 times slower than a quicksort or a mergesort, if you are sorting, say, integers).
You are unlikely to run into Combsort's (quadratic) worst case unless you deliberately engineer an input that will cause it.
