JP>> No.  Combsort is a variant on Bubble sort.  
 DN> Yes, but it's closer to Shell's algorithm in its strategy.
Yes, but it isn't Shell sort.  Comb Sort applies exactly the same 
modifications to Bubble Sort that Shell Sort applies to Insertion Sort.  When 
the gap size is 1, Comb Sort becomes Bubble Sort, in the same way that Shell 
Sort becomes Insertion Sort.
 DN> Since you now have my function template for Shell's algorithm, you
 DN> might care to give it a try. The version I posted is not O(n**2), but
 DN> O(n**1.5), so it should be significantly quicker than Combsort as the
 DN> array size increases.
I find, upon re-reading the literature, that there is controversy as to 
whether Shell sort is O(N**1.5) or O(N*log N).  No-one has been able to 
analyse the algorithm well enough to show which -- if, indeed, either.  Since 
both Shell and Comb apply the same modifications to algorithms that are 
themselves O(N*N), and since this yields O(N**1.5) or O(N*long N) in Shell's 
case, I suspect that, contrary to my previous message, Comb is probably 
O(N**1.5) or O(N*log N) too.
 JP>> The C Standard says *nothing* about which algorithm qsort() 
 JP>> may use.  It merely requires that it sort the elements of 
 JP>> the array.  A C implementation could use Bubble sort and 
 JP>> still remain conforming.
 DN> In that case, it is "misleading advertising". That's nothing new in
 DN> the software business, though. ... :-(
The reasons for not specifying the Quick Sort in the C Standard were twofold. 
 First, it would preclude the use of a better sort algorithm if one were to 
be discovered later.  Second, it would preclude intelligent implementations 
from choosing amongst multiple sort algorithms based upon array size and VM 
performance constraints (The VM behaviour of an internal sort algorithm is 
invariably not discussed in textbooks on algorithmics.).
 ¯ JdeBP ®
--- FleetStreet 1.19 NR
---------------