#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

void mergeSort(double *arr, size_t start, size_t end)
{
    //Если серия меньше двух, выходим из цикла
    if (end - start < 2)
        return;
    //Если кол-во равно двум, то перемещаем их
    if (end - start == 2)
    {
        if (arr[start] > arr[start + 1])
            swap(arr[start], arr[start + 1]);
        return;
    }
    //рекурсия функции
    mergeSort(arr, start, start + (end - start) / 2);
    //рекурсия функции
    mergeSort(arr, start + (end - start) / 2, end);
    //создаем массив, тип double
    vector<double> b;
    size_t b1 = start; //начальный элемент
    size_t e1 = start + (end - start) / 2; //середина
    size_t b2 = e1; //середина, копия

    //цикл по значениям
    while (b.size() < end - start)
    {
        //Если значение b1 больше середины массива, или , b2 меньше конца и значение b2 меньше или равно  b1
        //добавляем в b2, в ином случае в b1
        if (b1 >= e1 || (b2 < end && arr[b2] <= arr[b1]))
        {
            b.push_back(arr[b2]);
            ++b2;
        }
        else
        {
            b.push_back(arr[b1]);
            ++b1;
        }
    }
    //Цикл по массиву arr, ставим значение b
    for (size_t i = start; i < end; ++i)
        arr[i] = b[i - start];
}

int main()
{
    setlocale(LC_ALL, "rus");
    double n = 0, nap = 0;
    cout << "¬ведите количество чисел: ";
    cin >> n;
    cout << "1) —ортировка по возрастанию"<<endl<<"2) —ортировка по убыванию "<<endl;
    cin >> nap;
    double *arr = new double[n];
    double a;
    cout << "¬ведите  числа: ";
    for (int i = 0; i < n; i++) {
        //cout << i << "-ое число: ";
        cin >> arr[i];
    }
    cout << "»сходный массив: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    mergeSort(arr, 0, n);
    cout << "ќтсортированный массив: ";
    if (nap == 1) {
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
    }
    if (nap == 2) {
        for (int i = n - 1; i >= 0; i--) {
            cout << arr[i] << " ";
        }
    }
    cout << endl;
    system("pause");
    return 0;
}