Comb Sort - Just As Good As Quick Sort | Hacker News Reader

Comb Sort - Just As Good As Quick Sort

en.wikipedia.org

31 pointssamratjp9 comments

The guy who originally devised the algorithm is a professor at the University of Guelph, in Ontario, Canada. He's a pretty interesting professor - escaped from being drafted into the Polish army during World War II, wrote some of TCP at Stanford in the 70's, somehow ended up teaching networking, operating systems, and some other random subjects in an off-the-beaten-path Canadian school that's mostly known for farming.

I'm a student there; it's neat to see an article about his creation pop up. :)

Heh. I was excited to see it as well. I originally thought you had posted it when I saw it.

The article neither claims, nor offers any evidence, that comb sort is "just as good as quick sort"; could someone fix the title here, please?

I'd guess that it probably performs about as well as Shell sort: hard to analyse, strongly dependent on the detail of how your increments are chosen, typically worse than O(n log n).

I'm going to need some citations before I believe that it's just as good as quick sort.

Sorry if this is too meta but:

I usually think the wikipedia.org items on HN are just a silly waste of time (e.g, not news) but I do have to admit that this one got me. Neat algorithm. Hadn't heard of it prior and wouldn't have thought of it spontaneously.

I like the occasional wikipedia article on HN. They are often illuminating and amusing.

Does anyone know of a proof that this really is an $O(n log n)$ sort? I can sort of see it intuitively, but I can't quite convince myself it is true.

I'd guess it is generally O(n log n) for random data, but not mathematically. At least seems to me that an for an inverted range (n, n-1, n-2, ... 0) the algorithm will come down to O(n^2). I could be wrong though, didn't really think about it for that long.

Edit: I might be in the wrong here. I did some quick tests with this code (http://yagni.com/combsort/combsort.py) and did not find it to be much slower when data is a reversed range vs. sorted range. So much for that intuitive thought.

It is not O(n log n) — neither is quicksort for that matter :)

The comb sort is intuitively O(n²). The inner loop will run n - gap iterations, where gap starts at n / 1.25 and decrease toward 1. I think we can effectively count this as O(n).

The outer loop is more tricky, in the worst case it will run until n < 1.25^m (where m is number of iterations).

Edit: Just re-read the algorithm and I overlooked that the outer loop stops when gap is below one AND no swaps were performed, so the above is optimistic. I.e. it is very clearly O(n²) and if you want to be exact, it could actually be something like O(n × (n + log n)) (for a shrink factor of 2, to make it simple) — but more detailed study of the algorithm is required to arrive at the exact worst running time, as the “preprocessing” (where gap > 1 is going to affect how many swaps can be performed when gap = 1).

Reply on news.ycombinator.com