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

#define NITEMS 32

void print_tab(int* tab, int size) {
  int i;
  for(i=0; i<size; i++) {
    printf(" %d ", tab[i]);
  }
}

/* merge the sorted arrays tab1 and tab2 */
int* merge(int* tab1, int*tab2, int size) {
  int *res = malloc(sizeof(int)*(2*size));

  int i, i1, i2;
  i1 = 0;
  i2 = 0;
  /* merge until either tab1 or tab2 is finished */
  for(i=0; i1<size && i2<size; i++) {
    if(tab1[i1] < tab2[i2]) {
      res[i] = tab1[i1];
      i1++;
    } else if(tab1[i1] >= tab2[i2]) {
      res[i] = tab2[i2];
      i2++;
    }
  }

  /* either tab1 or tab2 is completely merged. Let's merge the remaining */
  for(; i1<size; i++) {
      res[i] = tab1[i1];
      i1++;
  }
  for(; i2<size; i++) {
      res[i] = tab2[i2];
      i2++;
  }
  return res;
}

int* sort(int* tab, int size) {

  if(size == 1) {
    int* res = malloc(sizeof(int));
    *res = tab[0];
    return res;
  }
  /* call recursively sort on the 2 sub arrays [0..n/2] and [n/2, n] */
  int *tab1 = sort(tab, size/2);
  int *tab2 = sort(&tab[size/2], size/2);

  /* merge the (sorted) arrays tab1 and tab2 into res */
  int *res = merge(tab1, tab2, size/2);
  free(tab1);
  free(tab2);
  /* res is sorted ! */
  return res;
}

int main() {
  int* tab = malloc(sizeof(int)* NITEMS);
  int i;
  for(i=0; i<NITEMS; i++) {
    tab[i] = rand()%NITEMS;
  }

  printf("Before sorting, tab contains:\n");
  for(i=0; i<NITEMS; i++) {
    printf(" %d ", tab[i]);
  }
  printf("\n");


  int *tab_out = sort(tab, NITEMS);
  free(tab);
  printf("After sorting, tab contains:\n");
  for(i=0; i<NITEMS; i++) {
    printf(" %d ", tab_out[i]);
  }
  printf("\n");
  free(tab_out);
  return EXIT_SUCCESS;
}