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

// Juntar dois subarrays do array[].
// Primeiro subarray é array[esquerda..meio]
// Segundo subarray é array[meio+1..direita]

void merge(int array[], int esquerda, int meio, int direita)
{
    int i, j, k;
    int tamanho_1 = meio - esquerda + 1;//tamanho do primeiro subarray
    int tamanho_2 = direita - meio;//tamanho do segundo subarray

    /* criar arrays temporários */
    int sEsquerda[tamanho_1], sDireita[tamanho_2];

    /* Copiar os valores para suas respectivas partes*/
    for (i = 0; i < tamanho_1; i++)
        sEsquerda[i] = array[esquerda + i];
    for (j = 0; j < tamanho_2; j++)
        sDireita[j] = array[meio + 1 + j];

    /* Juntar os subarrays da direira e esquerda para o array[]*/
    i = 0; // Indice inicial do primeiro subarray
    j = 0; // Indice inicial do segundo subarray
    k = esquerda; /* Indice apontando para a primeira
    posição do array a ser trabalhada*/

    while (i < tamanho_1 && j < tamanho_2) {
        //comparando elementos em posições ainda não mescladas nos dois
        //subarrays, o menor elemento é mesclado...
        if (sEsquerda[i] <= sDireita[j]) {
            array[k] = sEsquerda[i];
            i++;
        }
        else {
            array[k] = sDireita[j];
            j++;
        }
        k++;
    }

    /* copiar o restantes elementos do subarray da esquerda, se
    tiver algum*/
    while (i < tamanho_1) {
        array[k] = sEsquerda[i];
        i++;
        k++;
    }

    /* copiar o restantes elementos do subarray da direita, se
    tiver algum */
    while (j < tamanho_2) {
        array[k] = sDireita[j];
        j++;
        k++;
    }
}

void mergeSort(int array[], int esquerda, int direita)
{
    if (esquerda < direita) {
        //Para calcular o ponto médio podemos também usar (esquerda + direita)/2,
        //mas usando este jeito não estariamos a evitar overflow para limites
        //gigantescos
        int meio = esquerda + (direita - esquerda) / 2;
                mergeSort(array, esquerda, meio);
        mergeSort(array, meio + 1, direita);
        merge(array, esquerda, meio, direita);
    }
}
int main()
{
    int array[] = { 1, 4, 6, 7, 2, 3 };
    int tamanho = sizeof(array) / sizeof(array[0]);
    mergeSort(array, 0, tamanho - 1);
    printf("ARRAY ORDENADO\n");
    for(int i= 0; i<tamanho; i++)
            printf("%d ", array[i]);
    return 0;
}