MergeSort_commented

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

int Min(int a, int b)//функция вернет минимальное число из a и b
{
    if(a<b)
        return a;
    else
        return b;
}

int* Cpy(int* B, int* Arr, int left, int right, int& k)//функция копирует хвост одного массива в другой начиная с позиции left и заканчивая позицией right
{
    for (int i = left; i <= right; i++)
    {
        B[k] = Arr[i];
        k++;
    }
    return B;
}

void MergeSort(int*Arr, int kn, int deg)//алгоритм сортировки слиянием массива Arr длиной kn кусочками по deg
{
    int* B = new int[kn];
    int i = 0, j = deg;
    int k = 0;
    int p = j;
    int q = Min(kn - j, p);
    int l = 0, r = 0;


    while (j < kn)
    {
        l = r + p;
        r = l + q;
        while (i < l && j < r)
        {
            if (Arr[i] < Arr[j])
            {
                B[k] = Arr[i];
                i++;
            }
            else
            {
                B[k] = Arr[j];
                j++;
            }
            k++;

        }
        if (i == l)
            B = Cpy(B, Arr, j, r - 1, k);
        else if (j==r)
            B = Cpy(B, Arr, i, l - 1, k);
        i = r;
        j = r + p;
        q = Min(kn - j, p);
    }



    if (i < kn)
        B = Cpy(B, Arr, i, kn - 1, k);
    for (int i = 0; i < kn; i++)
        Arr[i] = B[i];
    delete[]B;
}

int* Merge(int* B, int n, int size)//задание - сортировка массива B слиянием.
{
    for (int i = n; i < size; i += n)
        MergeSort(B, size, i);

    return B;
}

int main()
{
    setlocale(0, "");
    int k, n;
    cout << "Введите количество отсортированных последовательностей: " << endl;
    cin >> k;
    cout << "Введите длину отсортированных последовательностей: " << endl;
    cin >> n;

    int** arr = new int*[k];//выделения памяти для матрицы в k строк, каждая из которых по
    for (int i = 0; i < k; i++)
        arr[i] = new int[n];//n элементов

    for (int i = 0; i < k; i++)
    {
        cout << "Введите последовательность № " << i+1 << endl;
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];//ввод последовательностей
    }
    int starttime = clock();//запоминаем время начала алгоритма
    int* B = new int[n*k];//создаем массив длинной k*n элементов

    for (int i = 0; i < k; i++)
        for (int j = 0; j < n; j++)
            B[i*n+j] = arr[i][j];

    cout << endl << "Исходный массив NK: " << endl;
    for (int i = 0; i < n*k; i++)
        cout << B[i] << ' ';
    cout << endl << endl;

    B = Merge(B, n, n*k);

    int dlitelnost = clock() - starttime;
    cout << "Время выполенения алгоритма " <<dlitelnost<<" миллисекунд"<<endl;
    //cout << "Желаемое время выполнения " <<n*log(n)<<" миллисекунд"<<endl;
    cout << "Получившийся массив NK: " << endl;
    for (int i = 0; i < n*k; i++)
        cout << B[i] << ' ';

    return 0;
}