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

void merge(int *A, int esq, int meio, int dir){
    int *v = (int *) malloc((dir - esq + 1) * sizeof(int));
    int i = esq;
    int j = meio + 1;
    int k = 0;

    while(i <= meio && j <= dir){
        if(A[i] < A[j]){
            v[k] = A[i];
            i++;
        }else{
            v[k] = A[j];
            j++;
        }
        k++;
    }

    while(i <= meio){
        v[k] = A[i];
        i++;
        k++;
    }

    while(j <= dir){
        v[k] = A[j];
        j++;
        k++;
    }

    for(i = 0; i < k; i++)
        A[esq + i] = v[i];
}

void merge_sort(int *A, int esq, int dir){
    if(esq < dir){
        int meio = (esq + dir) / 2;
        merge_sort(A, esq, meio);
        merge_sort(A, meio + 1, dir);
        merge(A, esq, meio, dir);
    }
}

int main(){
	int i, A[5] = {4, 7, 1, 5, 3};

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

    printf("\n");
	merge_sort(A, 0, 4);

	for(i = 0; i < 5; i++)
        printf("%d ", A[i]);
}