#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(const int i){
    unsigned int counter = 0;
    while(i&(~0<<counter)){
        counter++;
    }
    return counter;
}

void quicksort(void *base_,const size_t num_,const size_t size
    ,int (*compare)(const void *,const void *))
{
    void *base,*temp = alloca(size);
    quicksort_stack_body_t *stack
        = alloca(sizeof(quicksort_stack_body_t)*fls(num_));
    size_t stack_pos = 0,pivot,first2last,last2first,num;
    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){
                        pivot = pivot^last2first^first2last;
                    }
                    memcpy(temp,base+size*first2last,size);
                    memcpy(base+size*first2last,base+size*last2first,size);
                    memcpy(base+size*last2first,temp,size);
                }
            }
            if(num < first2last*2){
                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++;
        }
    }
    return;
}

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_;
    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() : 140000
quicksort() 100000