#include <iostream>
using namespace std;
void mergeArr(int first,int mid,int last,int a[],int tmp[]){
    int i = first;
    int j = mid+1;
    int n = mid ;
    int m = last;
    int k = 0;
    while (i<=n&&j<=m) {
        if (a[i]<a[j]) {
            tmp[k++] = a[i++];
        }else{
            tmp[k++] = a[j++];
        }

    }
    while (i<=n) {
        tmp[k++] = a[i++];
    }
    while(j<=m) {
        tmp[k++] = a[j++];
    }
    for (int i=0; i<k; i++) {
        a[first+i] = tmp[i];
    }
}

void mergeSort(int first ,int last,int a[],int tmp[]){
    if (first<last) {
        int mid = (first+last)/2;
        mergeSort(first, mid, a, tmp);
        mergeSort(mid+1, last, a, tmp);
        mergeArr(first, mid, last, a, tmp);
    }
}

void MergeSort(int n,int a[]){
    int *tmp = new int[n];
    mergeSort(0, n-1, a, tmp);
    delete [] tmp;
}
int main(int argc, const char * argv[]) {
    int a[] = {2,4,1,8,6,7,9};
    MergeSort(7,a);
    for (int i=0; i<7; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}