/*
   Fusionne les vecteurs v1[a1:b1] et v2[a2:b2], supposés triés,
   et place le résultat dans le vecteur v3[], supposé distinct
   de v1[] et v2[] ainsi que de taille suffisante.
*/

static void fusion(int v1[], int a1, int b1,
                   int v2[], int a2, int b2,
                   int v3[])
{
  int  i1, i2, i3;

  for (i1 = a1, i2 = a2, i3 = 0; i1 <= b1 || i2 <= b2;)
    if (i1 > b1)
      v3[i3++] = v2[i2++];
    else
      if (i2 > b2)
        v3[i3++] = v1[i1++];
      else
        v3[i3++] = v1[i1] < v2[i2] ? v1[i1++] : v2[i2++];
}

/*
   Tri du vecteur v[a:b], par ordre croissant, en utilisant
   le vecteur v_aux[a:b] comme espace de travail auxiliaire
*/

static void tri_sousvecteur(int v[], int a, int b, int v_aux[])
{
  int n, c, i;

  n = b - a + 1;
  if (n < 2)
    return;

  c = a + (n + 1) / 2;
  tri_sousvecteur(v, a, c - 1, v_aux);
  tri_sousvecteur(v, c, b, v_aux);

  for (i = a; i <= b; i++)
    v_aux[i] = v[i];

  fusion(v_aux, a, c - 1,
         v_aux, c, b,
         v + a);
}

/*
   Tri du vecteur v de taille n, par ordre croissant, en utilisant
   le vecteur v_aux, de même taille, comme espace de travail auxiliaire
 */

void tri_fusion(int v[], int n, int v_aux[])
{
  tri_sousvecteur(v, 0, n - 1, v_aux);
}