#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.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 ID_STACK 1004

#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);
}
struct _stack {
  void *buff;
  int n;
  struct _stack *next;
};

struct _stack *root = 0;

void push(void *buff, int n, struct _stack **root) {
  struct _stack *newnode;
  if ((newnode = qzmalloc(sizeof(struct _stack), ID_STACK)) != 0) {
    newnode->buff = buff;
    newnode->n = n;
    newnode->next = *root;
    *root = newnode;
  }
}

int pop(void **buff, int *n, struct _stack **root) {
  struct _stack *top;
  if (*root != 0) {
    *buff = (*root)->buff;
    *n = (*root)->n;
    top = *root;
    *root = top->next;
    qzfree(top, ID_STACK);
    return 1;
  } else {
    return 0;
  }
}

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

  root = 0;
  push(buff, n, &root);

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

  for (;;) {
  label_stackpop:

    if (!(pop(&sort_buff, &sort_n, &root))) {
      break;
    }
    for (;;) {
      if (sort_n == 0) {
        goto label_stackpop;
      }
      
      if (sort_n == 1) {
        goto label_stackpop;
      }

      if (sort_n == 2) {
        if (f(sort_buff, sort_buff + size) > 0)
          swap(sort_buff, sort_buff + size, t, size);
        goto label_stackpop;
      }
      flag = 0;

      memcpy(pv, sort_buff, size);
      for (px = 1; px < sort_n; px++) {
        if (f((int *)(sort_buff + size * px), pv) > 0) {
          memcpy(pivot, sort_buff + size * px, size);
          flag = 1;
          break;
        } else if (f((int *)(sort_buff + size * px), pv) < 0) {
          memcpy(pivot, pv, size);
          flag = 1;
          break;
        }
      }
      
      if (!flag) {
        goto label_stackpop;
      }
      pi = sort_buff;
      qi = sort_buff + size * (sort_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);
      }
      push(pi, sort_n - (pi - sort_buff) / size, &root);
      sort_n = (pi - sort_buff) / size;
    }
  }
  qzfree(t, ID_TMP);
  qzfree(pivot, ID_PIVOT);
  qzfree(pv, ID_PV);
  assert(root == 0);
}

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;

  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,