# What would be the performance properties of a comb or shell sort where the gap sequence is the prime numbers?

In particular, the genesis of this idea was the notion that you could minimize the number of passes through the list in a comb sort by using the primes as a way to guarantee that every element gets sorted while having the largest gap be only slightly larger than the square root of the size of the list rather than just below the size of the list. Some quick experimentation showed that this was very wrong and that starting with the largest prime possible as the gap is always more efficient (for comb sort; I confess I don't really get shell sort and so didn't test it, though I expect similar results) unless the list is already extremely well-ordered, so that part of the idea is a bust, but I'm still curious about the relative merits of using primes over other gap-choosing strategies.

I assume that this is obvious enough of an idea that it's been studied and found inefficient in some key way, but I don't have any idea why exactly this might be so beyond an aversion to having a lookup table of primes in one's code (or needing to calculate a significant number of primes every time the sort is run); I couldn't begin to speculate as to how costly that kind of overhead would be considered to be however.

• For a start, there are about $n/\log n$ primes below $n$, hence the algorithm takes $\Theta(n^2/\log n)$ comparisons and swaps. That’s quite poor as sorting algorithms go, the usual ones being $O(n\log n)$. Feb 17 at 8:07

Analyzing various gap sequences is very difficult, but it is easy to see that this would require at least approximately $$n\cdot\pi(n)\sim n^2/\log(n)$$ passes, since you are looping over the entire array once per prime. This makes it worse than some other simple gap sequences, such as $$2^n\pm1$$ or $$(3^n-1)/2$$, which are known to take only $$\mathcal O(n^{3/2})$$ passes. The other issue is the amount of time and space it would take to generate the gap sequence.

Generally a good gap sequence should grow exponentially. Intuitively we want to make $$\mathcal O(\log(n))$$ loops through the entire array, and with each loop involving as few swaps as possible overall. This would get you closer to $$\mathcal O(n\log(n))$$ complexity. There's more details on the linked Wikipedia concerning the complexity of shellsort and picking gap sequences.