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

/*#define DEBUG*/

#if defined(DEBUG)
#include "qzmalloc.h"

#else
#define qzmalloc(x, y) malloc(x)
#define qzfree(x, y) free(x)
#define qzmallocdump()
#endif
#define ID_TMP 1001
#define ID_PV 1002
#define ID_PIVOT 1003

#define N 10
static int buff[N];

void swap(void *a, void *b, void *t, int size) {
  memcpy(t, a, size);
  memcpy(a, b, size);
  memcpy(b, t, size);
}

void myqsort(void *buff, int n, int size, int (*f)(const void *, const void *), int mark) {
  int px, flag;
  void *pi, *qi, *t, *pivot, *pv;

  if (n == 0)
    return;

  if (n == 1)
    return;

  if ((t = qzmalloc(size, ID_TMP)) == 0)
    return;

  if (n == 2) {
    if (f(buff, buff + size) > 0)
      swap(buff, buff + size, t, size);
    qzfree(t, ID_TMP);
    return;
  }

  flag = 0;
  if ((pv = qzmalloc(size, ID_PV)) == 0)
    return;
  if ((pivot = qzmalloc(size, ID_PIVOT)) == 0)
    return;

  memcpy(pv, buff, size);

  for (px = 1; px < n; px++) {
    if (f((int *)(buff + size * px), pv) > 0) {
      memcpy(pivot, buff + size * px, size);/*      pivot = *(int *)(buff + size * px);*/
      flag = 1;
      break;
    } else if (f((int *)(buff + size * px), pv) < 0) {
      memcpy(pivot, pv, size); /*       pivot = pv; */
      flag = 1;
      break;
    }
  }
  qzfree(pv, ID_PV);

  if (!flag) {
    qzfree(t, ID_TMP);
    qzfree(pivot, ID_PIVOT);
    return;
  }
  pi = buff;
  qi = buff + size * (n - 1);
  for (;;) {
    char c;
    while (f(pi, pivot) < 0)
      pi += size;
    while (f(qi, pivot) >= 0)
      qi -= size;

    if (qi < pi)
      break;

    swap(pi, qi, t, size);
  }
  myqsort(buff, (pi - buff) / size,       sizeof(int), (int (*)(const void *, const void *))f, 2);
  myqsort(pi,   n - ((pi - buff) / size), sizeof(int), (int (*)(const void *, const void *))f, 3);
  qzfree(t, ID_TMP);
  qzfree(pivot, ID_PIVOT);
}

int f(int *a, int *b) { return *a - *b; }

#define SEED 31415926
int main() {
  int i, flag, pos, n;

  n = N;
  srand(SEED);
  for (i = 0; i < n; i++)
    buff[i] = rand() % 3000;

/*  buff[0] = 5; buff[1] = 3; buff[2] = 3; n = 3; */
  myqsort(buff, n, sizeof(int), (int (*)(const void *, const void *))f, 1);
  
  flag = 0;
  for (i = 0; i < n; i++) {
    printf("%d,", buff[i]);
    if (i < n -1)
      if (!(buff[i] <= buff[i + 1])) {
        flag = 1;
        pos = i;
      }
  }
  putchar('\n');
  if (flag)
    printf("%d:%d > %d:%d, out of order.\n", pos, buff[pos], pos + 1, buff[pos + 1]);

  qzmallocdump();
  return 0;
}
/* end */

111,493,862,1456,1552,1691,1879,1936,1940,2125,