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

using namespace std;

unsigned long long sortTime, asignmentOperations, compareOperations;

/* Ïðîöåäóðà äëÿ ïðåîáðàçîâàíèÿ â äâîè÷íóþ êó÷ó ïîääåðåâà ñ êîðíåâûì óçëîì i,
÷òî ÿâëÿåòñÿ èíäåêñîì â arr[]. n - ðàçìåð êó÷è */
void heapify(int arr[], int n, int i) {
    int largest = i;
// Èíèöèàëèçèðóåì íàèáîëüøèé ýëåìåíò êàê êîðåíü
    int l = 2*i + 1; // ëåâûé
    int r = 2*i + 2; // ïðàâûé
// Åñëè ëåâûé äî÷åðíèé ýëåìåíò áîëüøå êîðíÿ
    if (l < n && arr[l] > arr[largest])
        largest = l;
// Åñëè ïðàâûé äî÷åðíèé ýëåìåíò áîëüøå, ÷åì ñàìûé áîëüøîé ýëåìåíò íà äàííûé ìîìåíò
    if (r < n && arr[r] > arr[largest])
        largest = r;
// Åñëè ñàìûé áîëüøîé ýëåìåíò íå êîðåíü
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest); // Ðåêóðñèâíî ïðåîáðàçóåì â äâîè÷íóþ êó÷ó çàòðîíóòîå ïîääåðåâî
    }
}
// Îñíîâíàÿ ôóíêöèÿ, âûïîëíÿþùàÿ ïèðàìèäàëüíóþ ñîðòèðîâêó
void heapSort(int arr[], int n) {
    // Ïîñòðîåíèå êó÷è (ïåðåãðóïïèðóåì ìàññèâ)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // Îäèí çà äðóãèì èçâëåêàåì ýëåìåíòû èç êó÷è
    for (int i=n-1; i>=0; i--) {
        // Ïåðåìåùàåì òåêóùèé êîðåíü â êîíåö
        swap(arr[0], arr[i]);

        // âûçûâàåì ïðîöåäóðó heapify íà óìåíüøåííîé êó÷å
        heapify(arr, i, 0);
    }
}
void heapSortwithOperations(int arr[], int n) {
    for (int i = 1, j = i; i < n; i++, j = i) {
        while (j > 0 && arr[j] < arr[j - 1]) {
            compareOperations++;
            swap(arr[j], arr[j - 1]);
            asignmentOperations += 3;
            j--;
        }
        compareOperations++;
    }
}

void merge(int arr[], int a, int m, int b) {
    int i, j, k;
    int n1 = m - a + 1;
    int n2 = b - m;

    int lArr[n1], rArr[n2]; //temporary arrays

    /* copy data to temp arrays */
    for (int i = 0; i < n1; i++)
        lArr[i] = arr[a + i];
    for (int j = 0; j < n2; j++)
        rArr[j] = arr[m + 1 + j];

    i = j = 0; /* initial index of first sub-array and initial index of second sub-array */
    k = a;  /* initial index of merged sub-array */

    while (i < n1 && j < n2) {
        if (lArr[i] <= rArr[j]) {
            arr[k] = lArr[i++];
        } else {
            arr[k] = rArr[j++];
        }
        k++;
    }
    while (i < n1) {
        arr[k++] = lArr[i++];
    }
    while (j < n2) {
        arr[k++] = rArr[j++];
    }
}

void mergeSort(int arr[], int a, int b) {
    if (a < b) {
        int m = (a + b) / 2;
        mergeSort(arr, a, m);
        mergeSort(arr, m + 1, b);
        merge(arr, a, m, b);
    }
}

void mergewithOperations(int arr[], int a, int m, int b) {
    int i, j, k;
    int n1 = m - a + 1;
    int n2 = b - m;

    int lArr[n1], rArr[n2]; //temporary arrays

    /* copy data to temp arrays */
    for (int i = 0; i < n1; i++) {
        asignmentOperations++;
        lArr[i] = arr[a + i];
    }

    for (int j = 0; j < n2; j++) {
        asignmentOperations++;
        rArr[j] = arr[m + 1 + j];
    }

    i = j = 0; /* initial index of first sub-array and initial index of second sub-array */
    k = a;  /* initial index of merged sub-array */

    while (i < n1 && j < n2) {
        compareOperations++;
        if (lArr[i] <= rArr[j]) {
            arr[k] = lArr[i++];
            asignmentOperations++;
        } else {
            arr[k] = rArr[j++];
            asignmentOperations++;
        }
        k++;
    }
    while (i < n1) {
        arr[k++] = lArr[i++];
        asignmentOperations++;
    }
    while (j < n2) {
        arr[k++] = rArr[j++];
        asignmentOperations++;
    }
}

void mergeSortwithOperations(int arr[], int a, int b) {
    if (a < b) {
        int m = (a + b) / 2;
        mergeSortwithOperations(arr, a, m);
        mergeSortwithOperations(arr, m + 1, b);
        mergewithOperations(arr, a, m, b);
    }
}

int getRandom(int max) {
    return rand() % max + 1;
}

void generateRandom(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = getRandom(n);
    }
}

void generateGrowth(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = i;
    }
}

void generateDescending(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = n - i - 1;
    }
}

void heapSortBenchmark(int arr[], int n) {
    int bArr[n];

    for (int i = 0; i < n; i++)
        bArr[i] = arr[i];

    sortTime = clock();

    heapSort(bArr, n);

    sortTime = clock() - sortTime;

    for (int i = 0; i < n; i++)
        bArr[i] = arr[i];

    asignmentOperations = compareOperations = 0;

    heapSortwithOperations(bArr, n);

    cout << "Heap   sort   benchmark" << endl;
    cout << "n = " << n << endl;
    cout << "time = " << sortTime << " milliseconds" << endl;
    cout << "assignment operations = " << asignmentOperations << endl;
    cout << "comparison operations = " << compareOperations << endl;
    cout << "//////////////////////////////" << endl << endl;
}

void mergeSortBenchmark(int arr[], int n) {
        int bArr[n];

        for (int i = 0; i < n; i++)
                bArr[i] = arr[i];

        sortTime = clock();

        mergeSort(bArr, 0, n - 1);

        sortTime = clock() - sortTime;

            for (int i = 0; i < n; i++)
                bArr[i] = arr[i];

        asignmentOperations = compareOperations = 0;

        mergeSortwithOperations(bArr, 0, n - 1);

            cout << "Merge   sort   benchmark" << endl;
            cout << "n = " << n << endl;
            cout << "time = " << sortTime << " milliseconds" << endl;
            cout << "assignment operations = " << asignmentOperations << endl;
            cout << "comparison operations = " << compareOperations << endl;
            cout << "//////////////////////////////" << endl << endl;
}

void printArr(int *arr, int n) {
    for(int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;
}
int main() {
    int n;
    srand(time(NULL));

    int typeN[] = {10, 100, 1000, 10000};

    for (int i = 0; i < 4; i++) {

        n = typeN[i];
        int *arr = new int[n];

        cout << "by random: " << endl;
        generateRandom(arr, n);
        //printArr(arr, n);
        heapSortBenchmark(arr, n);
        mergeSortBenchmark(arr, n);

        cout << "by growth order: " << endl;
        generateGrowth(arr, n);
        //printArr(arr, n);
        heapSortBenchmark(arr, n);
        mergeSortBenchmark(arr, n);

        cout << "by descending order: " << endl;
        generateDescending(arr, n);
        //printArr(arr, n);
        heapSortBenchmark(arr, n);
        mergeSortBenchmark(arr, n);
    }

    return 0;
}