# Yet another quicksort

Code review my quicksort! It isn't supposed to be superfast or anything and doesn't basecase out to insertion sort or anything. It's optimized for clarity and only sorts arrays of pointers.

#define MISC_XCHG(a, b) ({ __typeof__(a) MISC_XCHG__A = (a); (a) = (b); (b) = MISC_XCHG__A; })

static void misc_qsort_internal(void const** A, void const** Z, bool (*cmp)(void const*, void const*))
{
while ((Z - A) > 1) {
/*
quicksort is a bit tricky. the basic idea of just partitioning
into < and >= partitions and recursing on each isn't guaranteed
to terminate, because everything can end up in the >= part.

the key to termination is to make sure at least one element
drops out.

the element that drops out must be equal to the pivot, so that
it can be >= everything in the < part and <= to everything in
the >= part. most simply, this element can be the pivot, which
should be inserted between the < and the >= parts.

so as we build up the regions we keep the pivot at the start of
the array and later exchange it with the last element in the <
part.
*/
void const* pivot = *A;

/* S points to the first element in the >= part */
void const** S = A+1;

for (void const** I = S; I < Z; I++) {
if (cmp(*I, pivot)) {
/* when *I < pivot */
/* we must exchange with the first element in the >= part */
MISC_XCHG(*I, *S);
/* and shift the >= part over by one */
S++;
} else {
/* when *I >= pivot */
/* nothing to do, the >= part grows "automatically" */
}
}

/* now do the business of exchanging the pivot */
void const** R = (S - 1);
*A = *R;
*R = pivot;

/* recursively sort (>=A, <R) and (>=S, <Z) */
/* recurse on the smaller partition */
/* this keeps stack usage always at or below O(log n) */
if ((R - A) < (Z - S)) {
misc_qsort_internal(A, R, cmp);
A = S; /* loop to sort (>=S, <Z) */
} else {
misc_qsort_internal(S, Z, cmp);
Z = R; /* loop to sort (>=A, <R) */
}
}
}

/*
cmp should return true iff [arg1] < [arg2] (strictly).
*/
static INLINE void misc_qsort(void const** A, uintptr_t L, bool (*cmp)(void const*, void const*))
{
misc_qsort_internal(A, (A + L), cmp);
}

#define MISC_QSORT_VARIANT(s, t)                                        \
static INLINE void misc_qsort_##s(t** A, uintptr_t L, bool (*cmp)(t const*, t const*)) \
{                                                                     \
misc_qsort(((void const**)(A)), L, ((bool (*)(void const*, void const*))(cmp))); \
}