#include <iostream>

void merge(int* data, int low, int mid, int high)
{
    int low_copy = low;
    int mid_copy = mid;

    int size = high - low;
    int* sorted = new int[size];
    int i = 0;

    while(low_copy < mid && mid_copy < high) {
        if(data[low_copy] < data[mid_copy]) {
            sorted[i] = data[low_copy++];
        }
        else {
            sorted[i] = data[mid_copy++];
        }
        ++i;
    }

    while(low_copy < mid) {
        sorted[i++] = data[low_copy++];
    }
    while(mid_copy < high) {
        sorted[i++] = data[mid_copy++];
    }

    for(i = 0; i < size; ++i) {
        data[low + i] = sorted[i];
    }
}

void recursive_merge_sort(int* data, int low, int high) {
    if(low >= high - 1) { return; }

    int mid = (high + low) / 2;
    recursive_merge_sort(data, low, mid);
    recursive_merge_sort(data, mid, high);

    merge(data, low, mid, high);
}

void merge_sort(int* data, int num_elements) {
    recursive_merge_sort(data, 0, num_elements);
}

int main()
{
    int data[] = { 5, 1, 4, 3, 65, 6, 128, 9, 0 };
    int num_elements = 9;

    std::cout << "unsortedn";
    for(int i=0; i < num_elements; ++i) {
        std::cout << data[i] << " ";
    }

    merge_sort(data, num_elements);

    std::cout << "nsortedn";
    for(int i=0; i < num_elements; ++i) {
        std::cout << data[i] << " ";
    }

    return 0;
}