#include "timer.h"

static long holdrand = 1L;

void srand ( unsigned int seed ) {
        holdrand = (long)seed;
}

int rand ( ) {
        return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}

typedef int T;
typedef int tblIndex;
#define compGT(a,b) (a > b)

tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
    T t, pivot;
    tblIndex i, j, p;

   /*******************************
    *  partition array a[lb..ub]  *
    *******************************/

    /* select pivot and exchange with 1st element */
    p = lb + ((ub - lb)>>1);
    pivot = a[p];
    a[p] = a[lb];

    /* sort lb+1..ub based on pivot */
    i = lb+1;
    j = ub;
    while (1) {
        while (i < j && compGT(pivot, a[i])) i++;
        while (j >= i && compGT(a[j], pivot)) j--;
        if (i >= j) break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
        j--; i++;
    }

    /* pivot belongs in a[j] */
    a[lb] = a[j];
    a[j] = pivot;

    return j;
}

void quickSort(T *a, tblIndex lb, tblIndex ub) {
    tblIndex m;

   /**************************
    *  sort array a[lb..ub]  *
    **************************/

    while (lb < ub) {
        /* partition into two segments */
        m = partition (a, lb, ub);

        /* sort the smallest partition    */
        /* to minimize stack requirements */
        if (m - lb <= ub - m) {
            quickSort(a, lb, m - 1);
            lb = m + 1;
        } else {
            quickSort(a, m + 1, ub);
            ub = m - 1;
        }
    }
}


int array[1000000];

int main ( ) {
	unsigned a;
	for ( a = 0; a < 1000000; a++ ) {
		array[a] = rand ( );
	}

	START_TIMER ( );
	quickSort ( array, 0, 1000000 - 1 );
	STOP_TIMER ( );
	return 0;

}