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

static void merge(int tab[], int lo, int mid, int hi, int aux[]);
static void mergeSortAux(int tab[], int lo, int hi, int aux[]);
void mergeSort(int tab[], int n);
  
static void merge(int tab[], int lo, int mid, int hi, int aux[]) {
  int i = lo, j = mid;

  for (int k = lo; k <= hi; k++)
    if (i == mid)
      aux[k] = tab[j++];
    else if (j == hi + 1)
      aux[k] = tab[i++];
    else if (tab[i] < tab[j])
      aux[k] = tab[i++];
    else
      aux[k] = tab[j++];

  for (int k = lo; k <= hi; k++)
    tab[k] = aux[k];
  
}
  
static void mergeSortAux(int tab[], int lo, int hi, int aux[]) {
  int n = hi - lo + 1;
  if (n <= 1)
    return;
  int mid = lo + (n + 1) / 2;
  mergeSortAux(tab, lo, mid - 1, aux);
  mergeSortAux(tab, mid, hi, aux);
  merge(tab, lo, mid, hi, aux);
}

void mergeSort(int tab[], int n) {
  int *aux = malloc(n*sizeof(int));
  mergeSortAux(tab, 0, n-1, aux);
  free(aux);
}

int main() {

  int tab[7] = {38, 27, 43, 3, 9, 82, 10};

  for(int i = 0; i < 7; i++)
    printf("%d ", tab[i]);
  printf("\n");
  
  mergeSort(tab, 7);

  for(int i = 0; i < 7; i++)
    printf("%d ", tab[i]);
  printf("\n");
  
  exit(0);
  
}