1/*
2 * A Killer Adversary for Quicksort
3 * M. D. MCILROY
4 * http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
5 *
6 * For comparison:
7 *  Bentley & McIlroy: 4096 items, 1645585 compares
8 *  random pivot:      4096 items, 8388649 compares
9 *  introsort:         4096 items, 151580 compares
10 *  heapsort:          4096 items, 48233 compares
11 */
12
13#include <stdio.h>
14#include <stdlib.h>
15
16static int *val;				/* item values */
17static int ncmp;				/* number of comparisons */
18static int nsolid;				/* number of solid items */
19static int candidate;				/* pivot candidate */
20static int gas;					/* gas value */
21
22#define freeze(x)	(val[(x)] = nsolid++)
23
24static int
25cmp(const void *px, const void *py)
26{
27	const int x = *(const int *)px;
28	const int y = *(const int *)py;
29
30	ncmp++;
31	if (val[x] == gas && val[y] == gas) {
32		if (x == candidate)
33			freeze(x);
34		else
35			freeze(y);
36	}
37	if (val[x] == gas)
38		candidate = x;
39	else if (val[y] == gas)
40		candidate = y;
41	return val[x] > val[y] ? 1 : val[x] < val[y] ? -1 : 0;
42}
43
44int
45antiqsort(int n, int *a, int *ptr)
46{
47	int i;
48
49	val = a;
50	gas = n - 1;
51	nsolid = ncmp = candidate = 0;
52	for (i = 0; i < n; i++) {
53		ptr[i] = i;
54		val[i] = gas;
55	}
56	qsort(ptr, n, sizeof(*ptr), cmp);
57	return ncmp;
58}
59