/* Plauger's introspective sort function (CUJ Oct 99) */
#include <stdlib.h>
#include <string.h>

typedef int     (*cmp) (const void *, const void *);

#define BUF_SIZE    512         /* > 0, auto buffer size */
#define SORT_MAX    32          /* > 1, cutover for insertion sort */

static void     swap(char *qb, char *qe, size_t size)
{                               /* swap elements *qb and *qe */
    char            buf[BUF_SIZE];      /* chunk to copy on swap */
    size_t          ms;

    for (ms = size; 0 < ms;) {  /* swap as many as possible */
        size_t          m = ms < sizeof(buf) ? ms : sizeof(buf);
        memcpy(buf, qb, m);
        memcpy(qb, qe, m);
        memcpy(qe, buf, m);
        ms -= m, qb += m, qe += m;
    }
}

static void     rotate(char *qb, char *qe, size_t size)
{                               /* right rotate [*qb, *qe] one place */
    char            buf[BUF_SIZE];      /* chunk to copy on rotate */
    size_t          ms,
                    mtot = qe - qb + size;

    for (ms = size; 0 < ms;) {  /* rotate as many as possible */
        size_t          m = ms < sizeof(buf) ? ms : sizeof(buf);
        memcpy(buf, qe + (size - m), m);
        memmove(qb + m, qb, mtot - m);
        memcpy(qb, buf, m);
        ms -= m;
    }
}

static void     adjust_heap(char *qb, size_t h, size_t n, size_t size, cmp compare)
{                               /* reheap item at h in heap (char
                                 * qb[size])[n] */
    size_t          h0 = h;
    size_t          k = 2 * h + 2;
    char           *qh = qb + h * size;
    char           *qk = qb + k * size;
    /* percolate hole out to larger/only child */
    for (; k <= n; k = 2 * k + 2, qk = qb + k * size) {
        if (k == n || compare(qk, qk - size) < 0)
            --k, qk -= size;
        swap(qh, qk, size);
        h = k, qh = qk;
    }
    /* percolate hole back in as far as h0 */
    for (; h0 < h;) {
        size_t          i = (h - 1) / 2;
        char           *qi = qb + i * size;
        if (compare(qh, qi) <= 0)
            break;
        swap(qi, qh, size);
        h = i, qh = qi;
    }
}

static void     intro_sort(char *qb, size_t n, size_t ideal, size_t size, cmp compare)
{
    for (; 0 < ideal && SORT_MAX < n;) {        /* quick sort with fat pivot */
        size_t          m = n / 2;
        char           *qm = qb + m * size;
        char           *qf = qb,
                       *ql = qb + n * size;

        if (compare(qm, qf) < 0)
            swap(qf, qm, size);
        if (compare(ql - size, qm) < 0)
            swap(qm, ql - size, size);
        if (compare(qm, qf) < 0)
            swap(qf, qm, size);

        for (;; qf += size) {   /* partition about pivot value */
            for (; qf < ql && compare(qf, qm) <= 0; qf += size);
            for (; qb < ql && compare(qm, ql -= size) <= 0;);
            if (ql <= qf)
                break;

            swap(qf, ql, size);
            if (qm == qf)
                qm = ql;
            else if (qm == ql)
                qm = qf;
        }
        ideal /= 2, ideal += ideal / 2;
        m = (ql - qb) / size + 1;
        n -= (qf - qb) / size;
        if (m <= n)
            intro_sort(qb, m, ideal, size, compare), qb = qf;
        else
            intro_sort(qf, n, ideal, size, compare), n = m;
    }

    if (SORT_MAX < n) {         /* heap sort */
        size_t          h;
        char           *qe;
        for (h = n / 2; 0 < h;)
            adjust_heap(qb, --h, n, size, compare);
        /* pop largest item to (shrinking) end */
        for (qe = qb + n * size; 1 < n;) {
            swap(qb, qe -= size, size);
            adjust_heap(qb, 0, --n, size, compare);
        }
    } else if (1 < n) {         /* insertion sort */
        char           *qm;
        /* percolate back elements [2, n) */
        for (qm = qb; 0 < --n;) {
            qm += size;
            if (compare(qm, qb) < 0)
                rotate(qb, qm, size);
            else {              /* scan backwards for insertion point */
                char           *qx = qm,
                               *qx0 = qm;
                for (; compare(qm, qx0 -= size) < 0; qx = qx0);
                if (qx != qm)
                    rotate(qx, qm, size);
            }
        }
    }
}

void            qsortI(void *base, size_t n, size_t size, cmp compare)
{                               /* sort (char base[size])[n] using introsort */
    intro_sort((char *) base, n, n, size, compare);
}