#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <chrono>

#define SIZE 10000
#define INFINITY 2147483647

using namespace std;

inline void RANDOM_ARRAY(vector<int>& v, int N) {
    srand(unsigned(time(0)));
    for(int i = 0; i < N; ++i)
        v.push_back(-N/2+rand()%N);
}



void bubbleSort(vector<int>&);
void merge(vector<int>&,int,int,int);
void mergeSort(vector<int>&,int,int);
void print(vector<int>&);
int main()
{
    vector<int> array;
    /*{-235, 234, -34, 235,  -3,
     -235,  34, 346,  23,2346,
      -34,-239, 983, 982, 348,
      845, 234};*/
    RANDOM_ARRAY(array, 10);
    //cout << "\nYou have " << array.size() << " elements in the array." << endl;
    //print(array);
    print(array);
    //print(array);
    for(int i = 100; i <= SIZE; i = 4*i) {
        array.clear();
        RANDOM_ARRAY(array,i);
        auto t1 = std::chrono::high_resolution_clock::now();
        bubbleSort(array);    // a function of your choice
        auto t2 = std::chrono::high_resolution_clock::now();
        cout << "With i = " << i << " bubbleSort() takes "
             << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
             << " milliseconds\n";
            // of course, you can replace both "nanoseconds" with "milliseconds" or "microseconds"
    }
    for(int i = 100; i <= 1000*SIZE; i = 4*i) {
    array.clear();
    RANDOM_ARRAY(array,i);
    //cout << "\nBefore sorting, array = " << endl; print(array);
    auto t1 = std::chrono::high_resolution_clock::now();
    mergeSort(array,0,i-1);    // a function of your choice
    auto t2 = std::chrono::high_resolution_clock::now();
    //cout << "\nAfter sorting, array = " << endl; print(array);
    cout << "With i = " << i << " mergeSort() takes "
         << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
         << " milliseconds\n";
        // of course, you can replace both "nanoseconds" with "milliseconds" or "microseconds"
    }

    return 0;
}

void bubbleSort(vector<int>& aRay) {
    int size = aRay.size();
    for(int i = 0; i < size-1; ++i) {
        for(int j = 0;j < size-i; ++j)
            if(aRay[j]>aRay[j+1]) {
                int temp = aRay[j];
                aRay[j]= aRay[j+1];
                aRay[j+1] = temp;
            }
    }
}

void merge(vector<int>& v, int p, int q, int r) {
    int n1 = q-p+1;
    int n2 = r-q;
    vector<int> L;
    for(int i= 0; i < n1; ++i)
        L.push_back(v.at(p+i));
    L.push_back(INFINITY);
    vector<int> R;
    for(int j= 0; j < n2; ++j)
        R.push_back(v.at(q+1+j));
    R.push_back(INFINITY);
    int i=0, j=0;
    for(int k = p; k <= r; ++k)
        if(L[i]<=R[j]) v[k]=L[i++];
        else v[k] = R[j++];
}


void mergeSort(vector<int>& v,int low,int high) {
    if(low<high) {
        int mid = (low+high)/2;
        mergeSort(v,low,mid);
        mergeSort(v,mid+1,high);
        merge(v,low,mid,high);
    }
}

void print(vector<int>& v) {
    for(int i = 0; i < v.size(); ++i) cout << v.at(i) << ", ";
    cout << endl;
}