#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <thread>
#include <fstream>
#define ARR_LEN 45'000
using namespace std;

void merge(int array[], int const left, int const mid,
           int const right)
{
    int const subArrayOne = mid - left + 1;
    int const subArrayTwo = right - mid;

    // Create temp arrays
    auto *leftArray = new int[subArrayOne],
            *rightArray = new int[subArrayTwo];

    // Copy data to temp arrays leftArray[] and rightArray[]
    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];

    auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
    int indexOfMergedArray = left;

    // Merge the temp arrays back into array[left..right]
    while (indexOfSubArrayOne < subArrayOne
           && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne]
            <= rightArray[indexOfSubArrayTwo]) {
            array[indexOfMergedArray]
                    = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else {
            array[indexOfMergedArray]
                    = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }

    // Copy the remaining elements of
    // left[], if there are any
    while (indexOfSubArrayOne < subArrayOne) {
        array[indexOfMergedArray]
                = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }

    // Copy the remaining elements of
    // right[], if there are any
    while (indexOfSubArrayTwo < subArrayTwo) {
        array[indexOfMergedArray]
                = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
    delete[] leftArray;
    delete[] rightArray;
}

// begin is for left index and end is right index
// of the sub-array of arr to be sorted
void mergeSort(int array[], int const begin, int const end)
{
    if (begin >= end)
        return;

    int mid = begin + (end - begin) / 2;
    mergeSort(array, begin, mid);
    mergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}

void bubbleSort(int arr[], int n)
{
    int i, j;
    bool swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = false;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }

        // If no two elements were swapped
        // by inner loop, then break
        if (!swapped)
            break;
    }
}

int main() {
    using std::chrono::high_resolution_clock;
    using std::chrono::duration_cast;
    using std::chrono::duration;
    using std::chrono::milliseconds;
    srand(time(nullptr));


    int nums1[ARR_LEN];
    int (*p1)[ARR_LEN] = &nums1;
    int nums2[ARR_LEN];

    for(int & i : nums1) {
        i = (int) rand() % 750 + 1;
    }

    copy(nums1, nums1+ARR_LEN, nums2);

    auto total1 = high_resolution_clock ::now();

    auto t1 = high_resolution_clock::now();
    bubbleSort(nums1, ARR_LEN);
//    mergeSort(nums1, 0, sizeof(nums1) / sizeof(nums1[0]));
//    thread merge (mergeSort, nums1, 0, sizeof(nums1) / sizeof(nums1[0]));
    auto t2 = high_resolution_clock::now();


    auto t3 = high_resolution_clock ::now();
    bubbleSort(nums2, ARR_LEN);
//    thread bubble (bubbleSort, nums2, ARR_LEN);
    auto t4 = high_resolution_clock ::now();

//    thread bubble2(bubbleSort, nums1, 0);


//    bubble2.join();
//    bubble.join();
    auto total2 = high_resolution_clock::now();

    auto ms1 = duration<double, std::milli>(t2-t1);
    auto ms2 = duration<double, std::milli>(t4-t3);
    auto total_time = duration<double, std::milli>(total2-total1);
    cout << "Merge sort took: "<< ms1.count() << "ms" << endl;
    cout << "Bubble sort took: " << ms2.count() << "ms" << endl;
    cout << "Total time: " << total_time.count() << "ms" << endl;

    return 0;
}