#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

template <typename T>
void merge(T array[], int left, int pivot, int right, T aux[]) {
    int i = left;
    int j = pivot;

    for(int a = left; a < right; a++) {
        aux[a] = array[a];
    }

    for(int k = left; k < right; k++) {
        if(i == pivot) {
            array[k] = aux[j];
            j++;
        } else if (j == right) {
            array[k] = aux[i];
            i++;
        } else {
            if(aux[i] < aux[j]) {
                array[k] = aux[i];
                i++;
            } else {
                array[k] = array[j];
                j++;
            }
        }
    }
}

template <typename T>
void mergesort(T array[], int left, int right, T aux[]) {
    if(left >= right) {
        return;
    }
    int pivot = (left+right)/2;
    mergesort(array, left, pivot, aux);
    mergesort(array, pivot + 1, right, aux);
    merge(array, left, pivot, right, aux);
}

template <typename T>
void mergesort(T array[]) {
    T aux[sizeof(array)/sizeof(array[0])];
    mergesort(array, 0, sizeof(array)/sizeof(array[0]), aux);
}

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int teste[] = { 5, 4, 2, 8, 9, 20 };

    for(int i = 0; i < sizeof(teste)/sizeof(teste[0]); i++) {
        cout << teste[i] << '\t';
    }
    cout << endl;

    mergesort(teste);

    for(int i = 0; i < sizeof(teste)/sizeof(teste[0]); i++) {
        cout << teste[i] << '\t';
    }
    cout << endl;

    return 0;
}