comb sort

The comb sort is a quick little sorting algorithm: nearly as fast as quick sort but without the intensive stack usage that comes from quick sort being recursive and much, much, much easier to program (that quick sort is a bitch)

The sort goes pretty much like this: You have a certain "gap", let's call it G, which starts a little below the length of the array, which we'll call L. You then iterate through the array, from I = 1 TO L-G (1 being the first position of the array), comparing the element at position I with the element at I+G. You then shrink G by a certain factor and iterate through the array again. You continue shrinking and iterating until the gap, G, is 1.

Here's the code in C (because who can read that generic algorithm language?):

#define SHRINK_FACTOR 0.6
void combsort(int *a, int len)
{
   int i, inc;
   double dinc = (double)len;
   do {
      dinc *= SHRINK_FACTOR;
      inc = (int)dinc;
      for(i = 0; i < len-inc; i++)
         if(a[i] > a[i+inc])
             swap(a[i], a[i+inc]);
   } while(inc > 1);
}