4 ms·
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.
by pmiller2 17y ago
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.
- asmosoinio 17y agoI'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 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.
- deleted 17y ago[deleted]
- sorbits 17y agoIt 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).