#include<stdio.h>

#define N 10

void merge(int * A, int low, int mid, int high)
{
    int m, n;
    m = mid - low + 1;
    n = high - mid;
    int a1[m],a2[n];

    for (int i = 0; i < m; i++)
        a1[i] = A[low + i];
    for (int j = 0; j < n; j++)
        a2[j] = A[mid + 1 + j];

    //compare two subsets, put lower one in sorted array
    int i = 0, j = 0, k = low;

    while (i < m && j < n)
    {
        if (a1[i] <= a2[j])
            A[k++] = a1[i++];
        else
            A[k++] = a2[j++];
    }

    //Insert remains
    while (i < m)
        A[k++] = a1[i++];
    while (j < n)
        A[k++] = a2[j++];
}

void mergeSort(int * A, int low, int high)
{
    if (low < high)
    {
        int mid = low + (high - low) / 2;
        mergeSort(A,low,mid);
        mergeSort(A,mid+1,high);
        merge(A,low,mid,high);
    }
}

int main(void)
{
    int A[N] = {12,63,58,95,41,35,65,0,38,44};

    mergeSort(A,0,N - 1);

    for (int i = 0; i < N; i++)
        printf("%3d",A[i]);

    putchar('\n');
    return 0;
}