#include <stdio.h>
#include <stdlib.h>

void printarr(int* arr, int begin, int end) {
    printf("%2d - %2d: ", begin, end);
    for(int i = begin; i < end; i++) {
        printf("%d, ", arr[i]);
    }
    printf("%d\n",arr[end]);
}

void mergesort(int* data, int begin, int end) {
    if(begin==end) return;
    int mid = (begin+end)/2;

    mergesort(data,begin,mid);
    mergesort(data,mid+1,end);

    int iter1 = begin;
    int iter2 = mid+1;
    int tmp;

    int * const merge = malloc((end-begin+1) * sizeof(int));

    int merge_i = 0;

    while(iter1 <= mid && iter2 <= end) {
        if(data[iter1] > data[iter2]) {
            merge[merge_i] = data[iter2];
            merge_i++;
            iter2++;
        } else {
            merge[merge_i] = data[iter1];
            merge_i++;
            iter1++;
        }
    }

    while(iter1 <= mid) {
        merge[merge_i] = data[iter1];
        merge_i++;
        iter1++;
    }

    while(iter2 <= end) {
        merge[merge_i] = data[iter2];
        merge_i++;
        iter2++;
    }

    for(int i = begin; i <= end; i++) {
        data[i] = merge[i-begin];
    }

    free(merge);
}

int main( int argc, char *argv[] ) {
	
    int a[10] = {5,0,2,4,9,1,3,8,6,7};

    mergesort(a, 0, 9);

    for(int i = 0; i < 10; i++) {
        printf("%d, ", a[i]);
    }
    printf("\n");
	return 0;
}