quicksort.h

typedef int (* cmpfn)(const void *a, const void *b);

/* interface */
void quicksort(void *pbase, size_t start, size_t end, size_t size,
  	cmpfn compare);


/* implementation */
void __insertion_sort(void *pbase, char *start, char *end, size_t size,
		cmpfn compare)
{
	char *sorted, *tmp, *p;
	for (sorted = start; sorted < end; sorted += size) {
		tmp = sorted;
		for (p = sorted + size; p <= end; p += size)
			if ((*compare)(p, tmp) < 0)
				tmp = p;
		swap(sorted, tmp, size);
	}
}

void quicksort(void *pbase, size_t start, size_t end, size_t size,
		cmpfn compare)
{
	if (start + 2 >= end) {
		__insertion_sort(pbase, (char*)(pbase + start * size),
				(char*)(pbase + end * size), size, compare);
		return;
	}

	int cmp;
	char *lt, *gt, *i, *x;
	char *base = (char *)pbase;
	lt = base + start * size;
	gt = base + end * size;
	i = lt + size;
	x = base + start * size;
	while (i <= gt) {
		cmp = (*compare)(i, x);
		if (cmp > 0) {
			swap(i, gt, size);
			gt -= size;
		} else if (cmp < 0) {
			swap(lt, i, size);
			lt += size;
			i += size;
		} else {
			i += size;
		}
	}
	quicksort(pbase, start, (lt - base) / size - 1, size, compare);
	quicksort(pbase, (gt - base) / size + 1, end, size, compare);
}