#include <chrono>
#include <iostream>

long getNanos()
{
    return std::chrono::high_resolution_clock::now().time_since_epoch().count();
}

int intKey(const int &i) { return i; }

static unsigned long seed = 0;

int randomInt()
{
    seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFF;
    return static_cast<int>(seed >> 17);
}

template <typename T> T *mergeSort(const T *in, int size, int (*key)(const T &))
{
    T *out = new T[size];
    for (int i = 0; i < size; ++i)
    {
        out[i] = in[i];
    }
    if (size <= 1)
    {
        return out;
    }

    // split
    int sizeLeft = size / 2;
    int sizeRight = (size + 1) / 2;
    T *left = out;
    T *right = out + sizeLeft;
    left = mergeSort(left, sizeLeft, key);
    right = mergeSort(right, sizeRight, key);

    // merge
    int rightCounter = 0;
    int leftCounter = 0;
    for (int i = 0; i < size; ++i)
    {
        if (leftCounter >= sizeLeft)
        {
            out[i] = right[rightCounter];
            ++rightCounter;
        }
        else if (rightCounter >= sizeRight)
        {

            out[i] = left[leftCounter];
            ++leftCounter;
        }
        else if (key(left[leftCounter]) < key(right[rightCounter]))
        {
            out[i] = left[leftCounter];
            ++leftCounter;
        }
        else
        {
            out[i] = right[rightCounter];
            ++rightCounter;
        }
    }
    delete[] right;
    delete[] left;
    return out;
}

void cacheTest()
{
    for (int size = 512; size < 100'000'000; size *= 2)
    {
        printf("Cache Test with size = %9d | ", size);
        constexpr int max = 500;
        int *a = new int[size];
        seed = 0;
        for (int i = 0; i < size; i++)
        {
            a[i] = randomInt() % max;
        }
        long time = -getNanos();
        int *b = mergeSort(a, size, intKey);
        time += getNanos();
        printf("%10ld ns | %7.2lf ns / entry \n", time,
               (static_cast<double>(time) / size));
        delete[] a;
        delete[] b;
    }
}

struct A
{
    int key;
    char filler[32];
};

int aKey(const A &a) { return a.key; }

void structTest()
{
    for (int size = 512; size < 100'000'000; size *= 2)
    {
        printf("Struct Test with size = %9d | ", size);
        constexpr int max = 500;
        A *a = new A[size];
        seed = 0;
        for (int i = 0; i < size; i++)
        {
            a[i].key = randomInt() % max;
        }
        long time = -getNanos();
        A *b = mergeSort(a, size, aKey);
        time += getNanos();
        printf("%10ld ns | %7.2lf ns / entry \n", time,
               (static_cast<double>(time) / size));
        delete[] a;
        delete[] b;
    }
}

int pointerKey(int *const &a) { return *a; }

void pointerTest()
{
    for (int size = 512; size < 100'000'000; size *= 2)
    {
        printf("Pointer Test with size = %9d | ", size);
        constexpr int max = 500;
        int **a = new int *[size];
        seed = 0;
        for (int i = 0; i < size; i++)
        {
            a[i] = new int(randomInt() % max);
        }
        long time = -getNanos();
        int **b = mergeSort<int *>(a, size, pointerKey);
        time += getNanos();
        printf("%10ld ns | %7.2lf ns / entry \n", time,
               (static_cast<double>(time) / size));
        for (int i = 0; i < size; i++)
        {
            delete a[i];
        }
        delete[] a;
        delete[] b;
    }
}

int main()
{
    cacheTest();
    structTest();
    pointerTest();
    return 0;
}