Yet another quicksort

Question

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))); \
  }

Answer 1

I think instead of writing the macro MISC_XCHG and using only once, I would just write the swap directly in place.

The use of upper-case for the single-letter locals is unconventional, and looks odd.

I haven't measured performance, but it seems that sorting already-ordered (or nearly-ordered) input is likely to suffer as a consequence of always picking the first element as pivot. A popular strategy is to pick the median of the first, last and central elements. It doesn't matter that these are not necessarily distinct when we get to the very smallest partitions.

I do like the code that chooses the smaller partition for the recursive step, and uses iteration on the larger partition.

I don't understand why L is a uintptr_t - I would have thought size_t the obvious choice, the same as standard qsort().

The cast of cmp from bool(*)(t const*, t const*) to (bool(*)(void const*, void const*) leads to Undefined Behaviour when it's called as the wrong type. The correct way to provide a type-specific comparator is to convert the arguments:

#define DEFINE_QSORT_COMPARATOR(s,t,cmp) \
  static bool qsort_compare_##s(void const *a, void const *b) \
  { t const *x = a; t const *y = b; return cmp(*x, *y); }