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

#define ARRAY_SIZE 1048576

typedef struct
{
    void *begin,*end;
} quicksort_stack_body_t;

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

#define SWAP(a,b,size) \
    do{ \
        register char *a_ = (char *)(a),*b_ = (char *)(b); \
        register size_t size_ = (size); \
        while(size_--){ \
            char temp = *a_; \
            *a_++ = *b_; \
            *b_++ = temp; \
        } \
    }while(0)

void quicksort(void *base,const size_t num,const size_t size
    ,int (*compare)(const void *,const void *))
{
    quicksort_stack_body_t *stack,*stack_top;
    stack_top = stack = alloca(sizeof(quicksort_stack_body_t)*fls(num));
    stack_top->begin = base,stack_top->end = base+size*(num-1);
    while(1){
        void *current_begin = stack_top->begin,*current_end = stack_top->end;
        if(current_begin >= current_end){
            if(stack == stack_top){
                break;
            }
            stack_top--;
        }
        else{
            void *pivot
                = current_begin+size*((current_end-current_begin)/size>>1)
                ,*first2last = current_begin,*last2first = current_end;
            while(first2last < last2first){
                while(compare(first2last,pivot)){
                    first2last += size;
                }
                while(!compare(last2first,pivot)){
                    last2first -= size;
                }
                if(first2last < last2first){
                    if(pivot == first2last){
                        pivot = last2first;
                    }
                    SWAP(first2last,last2first,size);
                }
            }
            SWAP(pivot,first2last,size);
            first2last += size;
            if(current_end-last2first < first2last-current_begin){
                stack_top->end = last2first;
                stack_top++;
                stack_top->begin = first2last;
                stack_top->end = current_end;
            }
            else{
                stack_top->begin = first2last;
                stack_top++;
                stack_top->begin = current_begin;
                stack_top->end = last2first;
            }
        }
    }
}

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_;
    /*
    while(counter != 32){
        array[counter] = rand()%64;
        printf("%02d ",array[counter]);
        counter++;
    }
    printf("\n");
    quicksort(array,32,sizeof(int),compare_integer_quicksort);
    counter = 0;
    while(counter != 32){
        printf("%02d ",array[counter]);
        counter++;
    }
    printf("\n");
    return 0;
    */
    srand(random_seed);
    while(counter != ARRAY_SIZE){
        array[counter] = rand()%1048576;
        counter++;
    }
    clock_ = clock();
    qsort(array,ARRAY_SIZE,sizeof(int),compare_integer_qsort);
    printf("C standard library - qsort() : %d/%d s\n",clock()-clock_,CLOCKS_PER_SEC);
    srand(random_seed);
    counter = 0;
    while(counter != ARRAY_SIZE){
        array[counter] = rand()%1048576;
        counter++;
    }
    clock_ = clock();
    quicksort(array,ARRAY_SIZE,sizeof(int),compare_integer_quicksort);
    printf("pi8027\'s quicksort() : %d/%d s\n",clock()-clock_,CLOCKS_PER_SEC);
    return 0;
}

C standard library - qsort() : 160000/1000000 s
pi8027's quicksort() : 200000/1000000 s