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

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).