#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

void Sliyanie(vector<int> &a, size_t start, size_t end)
{
    if (end - start < 2)
        return;
    if (end - start == 2)
    {
        if (a[start] > a[start + 1])
            swap(a[start], a[start + 1]);
        return;
    }
     //разделяем массив на две части
    Sliyanie(a, start, start + (end - start) / 2);//первая половина
    Sliyanie(a, start + (end - start) / 2, end);//вторая половина
    // в а лежат отсортированные половинки
    vector<int> b; //половинки в один массив
    size_t b1 = start; // начало первой половины
    size_t e1 = start + (end - start) / 2; //конец первой половины
    size_t b2 = e1; // начало второй половины
    while (b.size() < end - start) //перекидываем эл-ты массива а в b
    {
        if (b1 >= e1 || (b2 < end && a[b2] <= a[b1]))
        {
            b.push_back(a[b2]);
            ++b2;
        }
        else
        {
            b.push_back(a[b1]);
            ++b1;
        }
    }
    for (size_t i = start; i < end; ++i)
        a[i] = b[i - start];
}

int main()
{
    setlocale(LC_ALL,"rus");
    clock_t start;
    double duration;
    int N; cout << "Введите N: " << endl; cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; ++i)
        v[i]=rand()%N;
   for (auto i: v)
        cout << i << " ";
    cout << endl;
    start = clock();
    Sliyanie(v, 0, v.size());
    duration = (double)(clock()-start)/CLOCKS_PER_SEC;
    for (auto i: v)
        cout << i << " ";
    cout << endl;
    cout <<"Затраченное время: " << duration <<"сек."<<endl;
}