using System;

using static AlgosTri;

​

TestTri(new int[]{}); // tableau vide

TestTri(new int[]{ 1,2,3,4,5 }); // tableau déjà trié

TestTri(new int[]{ 5,1,4,2,3 }); // tableau en désordre, taille impaire

TestTri(new int[]{ 5,1,6,4,2,3 }); // tableau en désordre, taille paire

​

static void Afficher(int []tab)

{

   for(int i = 0; i != tab.Length; ++i)

      Console.Write($"{tab[i]} ");

   if (EstTrié(tab))

      Console.WriteLine("... il est donc trié");

   else

      Console.WriteLine("... il n'est donc pas trié");

}

static void TestTri(int [] tab)

{

   Console.Write("Avant : ");

   Afficher(tab);

   TriFusion(tab);

   Console.Write("Après : ");

   Afficher(tab);

}

static class AlgosTri

{

   public static void TriFusion(int[] vals) => TriFusion(vals, 0, vals.Length);

   static void TriFusion(int[] vals, int min, int max)

   {

      if (vals.Length <= SEUIL_FUSION)

         TriBulles(vals, min, max);

      else

      {

         int milieu = PointMilieu(min, max);

         TriFusion(vals, min, milieu);

         TriFusion(vals, milieu, max);

         Fusionner(vals, min, milieu, max);

      }

   }

   const int SEUIL_FUSION = 10; // arbitraire

   static void Fusionner(int[] vals, int min, int milieu, int max)

   {

      int i = min, j = milieu;

      // ceci est lâche; il y a une solution qui n'alloue pas de mémoire

      // mais elle est plus compliquée

      int[] temp = new int[Distance(min, max)];

      int n = 0;

      while (i != milieu && j != max)

      {

         if (vals[i] < vals[j])

            temp[n] = vals[i++];

         else

            temp[n] = vals[j++];

         ++n;

      }

      // ici, soit i == milieu, soit j == max donc une seule des

      // deux boucles va être utilisée

      while (i != milieu)

         temp[n++] = vals[i++];

      while (j != max)

         temp[n++] = vals[j++];

      // on recopie temp dans vals entre min et max

      for (int k = 0; k != temp.Length; ++k)

         vals[k + min] = temp[k];

   }

   public static void Permuter(ref int a, ref int b)

   {

      int temp = a;

      a = b;

      b = temp;

   }

   public static void TriBulles(int[] vals, int min, int max)

   {

      for (int i = min; i < max - 1; ++i)

         for (int j = i + 1; j < max; ++j)

            if (vals[j] < vals[i])

               Permuter(ref vals[i], ref vals[j]);

   }

   static int Distance(int min, int max) =>

      Math.Abs(max - min); // naïf : incorrect si signes différents

   static int PointMilieu(int min, int max) =>

      (min + max) / 2; // naïf : incorrect si min + max >= int.MaxValue

                       // (entre autres bogues)

   public static bool EstTrié(int [] tab)

   {

      for(int i = 1; i < tab.Length; ++i)

         if (tab[i] < tab[i-1])

            return false;

      return true;

   }

}

​