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

#define ARRAY_SIZE 1048576

typedef struct
{
    void *base;
    size_t num;
} quicksort_stack_body_t;

unsigned int fls(int i){
    unsigned int counter = 0;
    while(i){
        i = i>>1;
        counter++;
    }
    return counter;
}

void swap(void *a,void *b,size_t size)
{
    char temp;
    while(size){
        size--;
        temp = ((char *)a)[size];
        ((char *)a)[size] = ((char *)b)[size];
        ((char *)b)[size] = temp;
    }
}

void quicksort(void *base,size_t num,size_t size
    ,int (*compare)(const void *,const void *))
{
    quicksort_stack_body_t *stack
        = alloca(sizeof(quicksort_stack_body_t)*fls(num));
    size_t stack_pos = 0,pivot,first2last,last2first;
    if(!num){
        return;
    }
    stack[0].base = base,stack[0].num = num;
    while(1){
        base = stack[stack_pos].base,num = stack[stack_pos].num;
        pivot = 0,first2last = 0,last2first = num-1;
        while(pivot+1 != num && !compare(base+size*pivot,base+size*(pivot+1))
            && !compare(base+size*(pivot+1),base+size*pivot)){
            pivot++;
        }
        if(pivot+1 == num){
            if(!stack_pos){
                break;
            }
            stack_pos--;
        }
        else{
            if(compare(base+size*pivot,base+size*(pivot+1))){
                pivot++;
            }
            while(first2last < last2first){
                while(compare(base+size*first2last,base+size*pivot)){
                    first2last++;
                }
                while(!compare(base+size*last2first,base+size*pivot)){
                    last2first--;
                }
                if(first2last < last2first){
                    if(pivot == first2last){
                        pivot = last2first;
                    }
                    swap(base+size*first2last,base+size*last2first,size);
                }
            }
            if(num < first2last<<1){
                stack[stack_pos].num = first2last;
                stack[stack_pos+1].base = base+size*first2last;
                stack[stack_pos+1].num = num-first2last;
            }
            else{
                stack[stack_pos].base = base+size*first2last;
                stack[stack_pos].num = num-first2last;
                stack[stack_pos+1].base = base;
                stack[stack_pos+1].num = first2last;
            }
            stack_pos++;
        }
    }
}

int compare_integer_qsort(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

int compare_integer_quicksort(const void *a,const void *b)
{
    return *(int *)a<*(int *)b;
}

int main(void)
{
    int array[ARRAY_SIZE];
    unsigned long random_seed = time(NULL);
    size_t counter = 0;
    clock_t clock_;
    /*
    counter = 0;
    while(counter != 1024){
        array[counter] = rand()%128;
        counter++;
    }
    quicksort(array,1024,sizeof(int),compare_integer_quicksort);
    counter = 0;
    while(counter != 1024){
        printf("%d\n",array[counter]);
        counter++;
    }
    return 0;
    */
    srand(random_seed);
    while(counter != ARRAY_SIZE){
        array[counter] = rand()%128;
        counter++;
    }
    clock_ = clock();
    qsort(array,ARRAY_SIZE,sizeof(int),compare_integer_qsort);
    printf("C standard library - qsort() : %d\n",clock()-clock_);
    srand(random_seed);
    counter = 0;
    while(counter != ARRAY_SIZE){
        array[counter] = rand()%128;
        counter++;
    }
    clock_ = clock();
    quicksort(array,ARRAY_SIZE,sizeof(int),compare_integer_quicksort);
    printf("quicksort() %d\n",clock()-clock_);
    return 0;
}

C standard library - qsort() : 150000
quicksort() 80000