#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <memory.h>
#include <iostream>
#include <time.h>
#include <iomanip>
#include <time.h>
#include <sys/time.h>


const int SIZE = 15000000;


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


long currentTick() {
    struct timeval tv;
    gettimeofday( &tv, NULL );
    return (tv.tv_sec * 1000 + tv.tv_usec / 1000);
}


inline void swap(int *p1, int* p2) {
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}


inline int divide(int* start, int* end, int pivotIndex) {
    int len = end - start + 1;
    int pivot = start[pivotIndex];
    int storeIndex = 0;

    swap(&start[pivotIndex], &start[len-1]);
    for (int i=0; i<len-1; i++) {
        if (start[i] < pivot) {
            swap(&start[i], &start[storeIndex++]);            
        }
    }
    swap(&start[storeIndex], &start[len-1]);

    return storeIndex;
}


inline void mysort(int* start, int* end) {
    int len = end - start + 1;
    if (start >= end || len == 1) {
        return;
    }
    int pivotIndex = rand() % len;
    int newPivotIndex = divide(start, end, pivotIndex);
    mysort(&start[0], &start[newPivotIndex-1]);
    mysort(&start[newPivotIndex+1], end);
}


int main (int argc, char *argv[]) {
    long bytes = SIZE * sizeof(int);
    int* testData = (int*) malloc(bytes);
    int* testData2 = (int*) malloc(bytes);

    timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);

    std::cout << "Initializing random generator: [" << t.tv_sec << "]" << std::endl;
    srand(t.tv_sec);

    for (int x=0; x<SIZE; x++) {
        int val = rand();
        testData[x] = val;
        testData2[x] = val;
    }

    std::cout << "Sorting " << (bytes / 1024 / 1024) << " MB" << std::endl;
    std::flush(std::cout);

    long time1 = currentTick();
    mysort(&testData[0], &testData[SIZE-1]);
    long time2 = currentTick();
    std::cout << "My sort: " << (time2-time1) << " msec" << std::endl;

    time1 = currentTick();
    qsort(&testData2[0], SIZE, sizeof(int), compare);
    time2 = currentTick();
    std::cout << "Quicksort: " << (time2-time1) << " msec" << std::endl;
    assert(!memcmp(&testData[0], &testData2[0], bytes));   
    std::flush(std::cout);

    free(testData);
    free(testData2);
    return 0;
}