C quicksort

I have written quicksort in the past mostly to learn how it works and to play with optimization. (Because most of the time... I just want to call the system sort.)

Sometimes, knowing how this works helps with other problems, like sorting vectors, where we can do better than a full comparison on each step.

All of the other sorts I have written have been in a language that has at least some generic support. This time, though, it is in C, using void *'s.

And it wasn't that bad. This code is not fit for a system library, or anything like that, but it was fun(?) to write and test.

The code stops quicksorting when the subfile gets shorter than 10 lines, and it uses a median-of-three pivot selection.

In the testing I did, an iterative version of this algorithm showed no improvement.

void q4(void   *array,
        size_t  length,
        size_t  size,
        int(*compare)(const void *, const void *))
{
  if(length < 10) {
    for(void *a = array + size; a < array + size*length; a += size) {
      for(void *b = a;
          b > array && compare(b, b-size) < 0;
          b -= size) {
        swap(b, b-size, size);
      }
    }
  } else {
    void *middle = array + (length / 2) * size;
    void *outer = array + (length-1) * size;
    void *pivot = array + (length-2) * size;
    swap(middle, pivot, size);
    median_of_three(array, pivot, outer, size, compare);

    void *a = array - size;
    void * b = pivot;

    while(a < b) {
      a += size;
      for(;a < b && compare(a, pivot) < 0; a += size){}
      b -= size;
      for(;a < b && compare(pivot, b) < 0; b -= size){}
      if(a < b) {
        swap(a, b, size);
      }
    }

    assert(compare(a, pivot) >= 0);
    swap(a, pivot, size);
    q4(array, (a-array)/size, size, compare);
    q4(a + size, length - (a-array)/size-1, size, compare);
  }
}

The median of three code leaves the smallest value at a, the middle at b, and the largest at c.

void median_of_three(void *a, void*b, void*c, size_t size,
                     int (*compare)(const void*, const void*)) {
  if(compare(a, b) > 0) { swap(a, b, size); }
  if(compare(b, c) > 0) {
    swap(b, c, size);
    if(compare(a, b) > 0) { swap(a, b, size); }
  }
  assert(compare(a, b) <= 0);
  assert(compare(b, c) <= 0);
}

And the swap is not efficiency minded...

void swap(char *a, char *b, int size) {
  while(size > 0) {
    char t = *a;
    *a = *b;
    *b = t;
    ++a, ++b, --size;
  }
}

In most cases, the system qsort on my machine crushes this code.