#include <stdio.h>
#include <stdlib.h>  /* exit */

void printTab(int tab[], int size)
{
 int i;

 printf("{");
 for(i=0;i<=size-1;i=i+1)
 {
  if (i==size-1) printf("%d",tab[i]);
  else           printf("%d ",tab[i]);
 }
 printf("}");
}

void trace(int tab[], int size, int m)
{
 printf("%d   ",m);
 printTab(tab,size);
 printf("\n");
}

/* Retourne 1 (vrai) si le tableau est trie       */
/* Retourne 0 (faux) si le tableau n'est pas trie */
int estTrie(int tab[], int size)
{
 int trie = 1; /* vrai par defaut */
 int i;

 i = 1;
 while (trie && i<=size-1) /* Identique a : while (trie==1 && i<=size-1) */
 {
  if (tab[i-1]>tab[i])
  {
   trie = 0; /* faux */
  }
  i = i + 1;
 }

 return trie;
}

void copieSousTab(int tab[], int sousTab[], int inf, int sup)
{
 int i,j;
 j=0;
 for(i=inf; i<=sup; i=i+1)
 {
  sousTab[j]=tab[i];
  j=j+1;
 }
}

void fusion(int tab[], int g, int m, int d)
{
  int i;

  int nbElemsTab1 = m - g + 1;
  int tab1[nbElemsTab1];
  int i1;

  int nbElemsTab2 = d - m;
  int tab2[nbElemsTab2];
  int i2;
                                /* Copie, dans le tableau tab1, des elements */
  copieSousTab(tab,tab1,g,m);   /* de tab des indices g à m                  */
  copieSousTab(tab,tab2,m+1,d); /* Copie, dans le tableau tab2, des elements */
                                /* de tab des indices m+1 à d                */

  if (!estTrie(tab1,nbElemsTab1)) { printf("tab1 n'est pas trie\n"); exit(1); }
  if (!estTrie(tab2,nbElemsTab2)) { printf("tab2 n'est pas trie\n"); exit(1); }

  i1=0;
  i2=0;
  for(i=g; i<=d; i=i+1)
  {
   if (i1<=nbElemsTab1-1 && i2<=nbElemsTab2-1)
   {
    if (tab1[i1]<tab2[i2])
    {
     tab[i]=tab1[i1];
     i1=i1+1;
    }
    else
    {
     tab[i]=tab2[i2];
     i2=i2+1;
    }
   }
   else
   {                /* si l'un des tableaux est vide avant l'autre */
    if (i1<=nbElemsTab1-1)
    {
     tab[i]=tab1[i1];   /* tab2 est vide */
     i1=i1+1;
    }
    else
    {
     tab[i]=tab2[i2];   /* tab1 est vide */
     i2=i2+1;
    }
   }
  }
}

void triRecFusion(int tab[], int size, int depart, int arrivee)
{
 int n = size;

 if (depart<0   || depart >= size ||
     arrivee <0 || arrivee >= size)  { printf("Erreur depart ou arrivee\n");
                                       exit(1);
 }

 if (depart < arrivee)
 {
  int m = (depart+arrivee)/2;
         
  triRecFusion(tab,n,depart,m);
  triRecFusion(tab,n,m+1,arrivee);
  fusion(tab,depart,m,arrivee);
  /* trace(tab,size,m); */
 }
}

/* ************************************************** */

void triFusion(int tab[], int size)
{
 triRecFusion(tab,size,0,size-1);
}

int main(void)
{
 int tab[5]= {90,67,2,50,23};
 int taille = 5;

 printTab(tab,taille);
 printf("\n");

 triFusion(tab,taille);

 printTab(tab,taille);
 printf("\n");

 return 0;
}