#include <stdio.h>

void merge(int v[], int aux[], int p, int q, int r)
{
    int i, j, k;

    for (i = p; i <= r; ++i)
        aux[i] = v[i];
    
    for (i = p, j = q+1, k = p; k <= r; ++k)
        if ( i <= q && aux[i] <= aux[j] || j > r)
            v[k] = aux[i++];
        else
            v[k] = aux[j++];
}

void mergesort(int v[], int aux[], int p, int r)
{
    int q;
    if (p < r) {
        q = (p + r) / 2;
        mergesort(v, aux, p, q);
        mergesort(v, aux, q+1, r);
        merge(v, aux, p, q, r);
    }
}

int main()
{
    int i;
    int v[6] = {3, 4, 1, 2, 6, 5};
    int aux[6];
    
    for (i = 0; i < 6; ++i)
        printf("%d ", v[i]);
    printf("\n");
    
    mergesort(v, aux, 0, 5);

    for (i = 0; i < 6; ++i)
        printf("%d ", v[i]);
    printf("\n");

    return 0;
}