/*
 * A Killer Adversary for Quicksort
 * M. D. MCILROY
 * http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
 *
 * For comparison:
 *  Bentley & McIlroy: 4096 items, 1645585 compares
 *  random pivot:      4096 items, 8388649 compares
 *  introsort:         4096 items, 151580 compares
 *  heapsort:          4096 items, 48233 compares
 */

#include <stdio.h>
#include <stdlib.h>

static int *val;                                /* item values */
static int ncmp;                                /* number of comparisons */
static int nsolid;                              /* number of solid items */
static int candidate;                           /* pivot candidate */
static int gas;                                 /* gas value */

#define freeze(x)       (val[(x)] = nsolid++)

static int
cmp(const void *px, const void *py)
{
        const int x = *(const int *)px;
        const int y = *(const int *)py;

        ncmp++;
        if (val[x] == gas && val[y] == gas) {
                if (x == candidate)
                        freeze(x);
                else
                        freeze(y);
        }
        if (val[x] == gas)
                candidate = x;
        else if (val[y] == gas)
                candidate = y;
        return val[x] > val[y] ? 1 : val[x] < val[y] ? -1 : 0;
}

int
antiqsort(int n, int *a, int *ptr)
{
        int i;

        val = a;
        gas = n - 1;
        nsolid = ncmp = candidate = 0;
        for (i = 0; i < n; i++) {
                ptr[i] = i;
                val[i] = gas;
        }
        qsort(ptr, n, sizeof(*ptr), cmp);
        return ncmp;
}