#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <chrono>

using namespace std;
const int arr_size = 1000;

//функция, сливающая массивы

void Merge(int *A, int first, int last)
{
    int middle, start, final;
    int *mas = new int[arr_size];

    middle = (first + last) / 2;                        //вычисление среднего элемента
    start = first;                                      //начало левой части
    final = middle + 1;                                 //начало правой части

    for (int j = first; j <= last; j++)                 //выполнять от начала до конца
    {
        if ((start <= middle) && ((final > last) || (A[start] < A[final])))
        {
            mas[j] = A[start];
            start++;
        }
        else
        {
            mas[j] = A[final];
            final++;
        }
    }

    //возвращение результата в список

    for (int j = first; j <= last; j++)
    {
        A[j] = mas[j];
    }

    delete[]mas;
};

//рекурсивная процедура сортировки

void merge_sort(int *A, int first, int last)
{
    {
        if (first<last)
        {
            merge_sort(A, first, (first + last) / 2);   //сортировка левой части
            merge_sort(A, (first + last) / 2 + 1, last); //сортировка правой части
            Merge(A, first, last);                      //слияние двух частей
        }
    }
};



void main()
{

    int n = arr_size - 1;
    int *arr = new int[arr_size];


    for (int i = 1; i <= n; i++)
    {
        arr[i] = rand() % 1000;
    }

    auto begin = std::chrono::steady_clock::now();

    merge_sort(arr, 0, n);                                  //вызов сортирующей процедуры

    auto end = std::chrono::steady_clock::now();

    cout << "After Sorting: ";                          //вывод упорядоченного массива

    for (int i = 1; i <= n; i++)
    {
        cout << arr[i] << "\n ";
    }

    auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);

    cout << "The time: " << elapsed_ms.count() << " ns\n";


    delete[] arr;
    system("pause");

}