#include <iostream>
#include <time.h>
#include <ctime>
#include <stdlib.h>

#define n 1000

using namespace std;

void Merge(int* A, int first, int last, unsigned int& counter_e, unsigned int& counter_m){
    int middle, start, final, j;
    int* mas = new int[n];
    middle = (first + last) / 2;
    start = first;
    final = middle + 1;
    for (j = first; j <= last; j++) {
        if ((start <= middle) && ((final > last) || (A[start] < A[final]))) {
            counter_e++;
            counter_m++;
            mas[j] = A[start];
            start++;
        }
        else {
            counter_e++;
            counter_m++;
            mas[j] = A[final];
            final++;
        }
    }
    for (j = first; j <= last; j++) {
        A[j] = mas[j];
    }

    delete[]mas;
};

void MergeSort(int* A, int first, int last, unsigned int& counter_e, unsigned int& counter_m) {
    if (first < last) {
        MergeSort(A, first, (first + last) / 2, counter_e, counter_m);
        MergeSort(A, (first + last) / 2 + 1, last, counter_e, counter_m);
        Merge(A, first, last, counter_e, counter_m);
    }
};

int main(){

    srand(time(NULL));
    int i;

    unsigned int counter_e = 0;
    unsigned int counter_m = 0;

    int* A = new int[n];

    for (int i = 0; i < n; i++) {
        A[i] = rand() % 100;
    }
    clock_t time;
    time = clock();

    MergeSort(A, 1, n, counter_e, counter_m);

    delete[]A;

    time = clock() - time;

    cout << "Runtime is " << (double)time / CLOCKS_PER_SEC << endl;
    cout << "Number of comparisons:" << counter_m << endl << " Number of assignments: " << counter_e << endl << endl;

    return 0;
}