#include <iostream>

void TopDownMergeSort(int *a, int *b, int n);
void TopDownSplitMerge(int *a, int begin, int end, int *b);
void CopyArray(int *from, int begin, int end, int *to);
void TopDownMerge(int *a, int begin, int middle, int end, int *b);

void TopDownMergeSort(int *a, int *b, int n)
{
    TopDownSplitMerge(a, 0, n, b);
}

void TopDownSplitMerge(int *a, int begin, int end, int *b)
{
    if (end - begin < 2) {
        return;
    }

    int middle = (end + begin) / 2;
    TopDownSplitMerge(a, begin, middle, b);
    TopDownSplitMerge(a, middle, end, b);
    TopDownMerge(a, begin, middle, end, b);
    CopyArray(b, begin, end, a);
}

void TopDownMerge(int *a, int begin, int middle, int end, int *b)
{
    int i0 = begin, i1 = middle;

    for (int j = begin; j < end; j++) {
        if (i0 < middle && (i1 >= end || a[i0] <= a[i1])) {
            b[j] = a[i0];
            ++i0;
        } else {
            b[j] = a[i1];
            ++i1;
        }
    }
}

void CopyArray(int *from, int begin, int end, int *to)
{
    for (int k = begin; k < end; k++) {
        to[k] = from[k];
    }
}

int main(int argc, char const* argv[])
{
    int a1[] = {31, 20, 49, 2, 10, 22, 50};
    const int size = sizeof(a1) / sizeof(int);
    int *a2 = new int [size];

    TopDownMergeSort(a1, a2, size);

    for (int i = 0; i < size; ++i) {
        std::cout << a2[i] << ",";
    }
    
    return 0;
}