# Why is Comb-sort (aka Dobosiewicz-sort) faster than Cocktail-sort (aka shake-sort)?

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?

• What precisely do you mean by "faster"? – Ryan Mar 17 '15 at 17:56
• @Ryan: Comb-sort requires a much smaller amount of element-to-element comparisons for the sort. – Dun Peal Mar 17 '15 at 21:49
• Comparing these two bounds is not helpful, and neither implies how fast the respective algorithm is. – Raphael Jun 1 '15 at 13:32