#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

const int MILLION = 1000 * 1000;
const int N = 10 * MILLION;
const int TRIALS = 100;

static long nowUsec()
{
    struct timeval t;
    gettimeofday(&t, NULL);
    return t.tv_sec * MILLION + t.tv_usec;
}

// Internal

static int internal_compare(const void* x, const void* y)
{
    int a = *(int*) x;
    int b = *(int*) y;
    return a < b ? -1 : a > b ? 1 : 0;
}

static int* internalGenerateData(int n)
{
    int* data = (int*) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        data[i] = rand();
    }
    return data;
}

static void internalSort(int* data, int n)
{
    qsort(data, n, sizeof(int), internal_compare);
}

static long internalTimeScanUsec(int* data, int n, int trials)
{
    long start = nowUsec();
    for (int t = 0; t < trials; t++) {
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += data[i];
        }
    }
    long stop = nowUsec();
    return stop - start;
}

static void testInternal()
{
    int* data = internalGenerateData(N);
    internalSort(data, N);
    long usec = internalTimeScanUsec(data, N, TRIALS);
    double average = (double) usec / TRIALS;
    printf("INTERNAL time/scan (usec): %f\n", average);
}

// External sorted

static int external_compare(const void* x, const void* y)
{
    int a = **(int**) x;
    int b = **(int**) y;
    return a < b ? -1 : a > b ? 1 : 0;
}

static int** externalGenerateData(int n)
{
    int** pointers = (int**) malloc(sizeof(int*) * n);
    int* data = (int*) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        data[i] = rand();
        pointers[i] = &data[i];
    }
    return pointers;
}

static void externalSort(int** pointers, int n)
{
    qsort(pointers, n, sizeof(int*), external_compare);
}

static long externalTimeScanUsec(int** pointers, int n, int trials)
{
    long start = nowUsec();
    for (int t = 0; t < trials; t++) {
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += *pointers[i];
        }
    }
    long stop = nowUsec();
    return stop - start;
}

static void testExternal()
{
    int** pointers = externalGenerateData(N);
    long usecUnsorted = externalTimeScanUsec(pointers, N, TRIALS);
    double averageUnsorted = (double) usecUnsorted / TRIALS;
    printf("EXTERNAL UNSORTED time/scan (usec): %f\n", averageUnsorted);
    externalSort(pointers, N);
    long usecSorted = externalTimeScanUsec(pointers, N, TRIALS);
    double averageSorted = (double) usecSorted / TRIALS;
    printf("EXTERNAL SORTED time/scan (usec): %f\n", averageSorted);
    printf("SORTED/UNSORTED: %f\n", averageSorted / averageUnsorted);
}

// main

int main(int argc, const char * argv[])
{
    testInternal();
    testExternal();
    return 0;
}