Re: [RFC] 2.5.8 sort kernel tables

[Jamie Lokier <lk@tantalophile.demon.co.uk>]

Oliver Xymoron wrote:
> Combsort is a trivial modification of bubblesort that's O(n log(n)).
> 
>  http://cs.clackamas.cc.or.us/molatore/cs260Spr01/combsort.htm

Cute.  Combsort is very closely related to Shellsort, which is tiny,
fast and old (c.1959), yet its time complexity is still not well
understood:

   http://www.cs.princeton.edu/~rs/shell/shell.c
   http://www.cs.princeton.edu/~rs/shell/

The above paper mentions a variant of Shellsort which uses a "h-bubble"
operation.  Beware!  That does probabilistic sorting, which means
"nearly always sorts, with high probability"!

I think that Combsort is equivalent to that variant of Shellsort, with
larger constant factors in its time complexity (because bubbling is
slower than insertion), and it effectively degrades to Bubblesort in the
event that the probabilistic h-bubble Shellsort fails to sort.

There are a couple of improvements to h-bubble Shellsort mentioned in
the paper which may be faster.

enjoy,
-- Jamie