Re: [patch 1/13] Qsort

[hpa@zytor.com (H. Peter Anvin)]

Followup to:  <Pine.LNX.4.61.0501230600070.2748@dragon.hygekrogen.localhost>
By author:    Jesper Juhl <juhl-lkml@dif.dk>
In newsgroup: linux.dev.kernel
>
> On Sun, 23 Jan 2005, Andi Kleen wrote:
> 
> > > How about a shell sort?  if the data is mostly sorted shell sort beats 
> > > qsort lots of times, and since the data sets are often small in-kernel, 
> > > shell sorts O(n^2) behaviour won't harm it too much, shell sort is also 
> > > faster if the data is already completely sorted. Shell sort is certainly 
> > > not the simplest algorithm around, but I think (without having done any 
> > > tests) that it would probably do pretty well for in-kernel use... Then 
> > > again, I've known to be wrong :)
> > 
> > I like shell sort for small data sets too. And I agree it would be 
> > appropiate for the kernel.
> > 
> Even with large data sets that are mostly unsorted shell sorts performance 
> is close to qsort, and there's an optimization that gives it O(n^(3/2)) 
> runtime (IIRC), and another nice property is that it's iterative so it 
> doesn't eat up stack space (as oposed to qsort which is recursive and eats 
> stack like ****)...
> Yeah, I think shell sort would be good for the kernel.
> 

In klibc, I use combsort:

/*
 * qsort.c
 *
 * This is actually combsort.  It's an O(n log n) algorithm with
 * simplicity/small code size being its main virtue.
 */

#include <stddef.h>
#include <string.h>

static inline size_t newgap(size_t gap)
{
  gap = (gap*10)/13;
  if ( gap == 9 || gap == 10 )
    gap = 11;

  if ( gap < 1 )
    gap = 1;
  return gap;
}

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *))
{
  size_t gap = nmemb;
  size_t i, j;
  char *p1, *p2;
  int swapped;

  do {
    gap = newgap(gap);
    swapped = 0;

    for ( i = 0, p1 = base ; i < nmemb-gap ; i++, p1 += size ) {
      j = i+gap;
      if ( compar(p1, p2 = (char *)base+j*size) > 0 ) {
        memswap(p1, p2, size);
        swapped = 1;
      }
    }
  } while ( gap > 1 || swapped );
}