/* Tri par fusion d'un tableau d'entiers             */

import java.util.Random;

public class TriFusion {

  static long somme(int [] t) {
    long total = 0L;
    for ( int i = 0 ; i < t.length ; i++ ) {
      total = total+t[i]; }
    return total;
  }

  static boolean estTrie(int [] t) {
    boolean trie = true;
    int i = 0;
    while ( trie && ( i < t.length-1 ) ) {
      if ( t[i] > t[i+1] )
        trie = false;
      i++; }
    return trie;
  }

/* Fonction d'affichage des valeurs contenues        */
/* dans un tableau de int                            */
  
  static void affichageTableau(int [] t) {
    for ( int i = 0 ; i < t.length ; i++ ) {
      Ecran.formater("%4d",t[i]); }
    Ecran.sautDeLigne();
  }

/* Fonction de creation d'un tableau de n int        */
/* initialise avec des valeurs croissantes           */
  
  static int [] initRandCroissant(int n,long seed) {
    Random r = new Random(seed);
    int [] t = new int[n];
    t[0] =(int) (r.nextDouble()*10.0);
    for ( int i = 1 ; i < t.length ; i++ ) {
      t[i] = t[i-1] + (int) (r.nextDouble()*10.0); }
    return t;
  }

/* Fonction de creation d'un tableau de n int        */
/* initialise avec des valeurs croissantes           */
  
  static void initRandCroissant(int [] t,int deb,int n,long seed,int fact) {
    Random r = new Random(seed);
    t[deb] =(int) (r.nextDouble()*fact);
    for ( int i = 1 ; i < n ; i++ ) {
      t[i+deb] = t[i+deb-1] + (int) (r.nextDouble()*fact); }
  }

/* Fonction de creation d'un tableau de 10 int       */
/* initialise avec des valeurs croissantes           */
  
  static int [] initRandQuasiCroissant(int n,long seed) {
    Random r = new Random(seed);
    int [] t = initRandCroissant(n,seed);
    int nb = 10;
    int i1;
    int i2;
    int aux;
    for ( int i = 0 ; i < nb ; i++ ) {
      i1 =(int) (r.nextDouble()*(n+1));
      i2 =(int) (r.nextDouble()*(n+1));
      aux = t[i1];
      t[i1] = t[i2];
      t[i2] = aux; }
    return t;
  }

/* Fonction de creation d'un tableau de 10 int       */
/* initialise avec des valeurs tirees au sort        */
/* dans l'intervalle [0,1000[                        */
  
  static int [] initRand() {
    int [] t = new int[10];
    for ( int i = 0 ; i < t.length ; i++ ) {
      t[i] =(int) (Math.random()*1000.0); }
    return t;
  }

/* Fonction de creation d'un tableau de n int        */
/* initialise avec des valeurs tirees au sort        */
/* dans l'intervalle [0,max]                         */
/* avec initialisation du generateur de nombres      */
/* aleatoires a la valeur seed                       */
  
  static int [] initRand(long seed,int n,int max) {
    Random r = new Random(seed);
    int [] t = new int[n];
    for ( int i = 0 ; i < t.length ; i++ ) {
      t[i] =(int) (r.nextDouble()*(max+1)); }
    return t;
  }

///////////////////////////////////////////////////////
  
/* Action de fusion en un tableau trié               */
/* de deux sous-tableaux contigus triés              */
/* définis au sein d'un tableau d'entiers            */
/* Le sous-tableau 1 contient les t1 entiers         */
/* situés à partir de l'indice i1                    */
/* Le sous-tableau 2 contient les t2 entiers         */
/* situés à partir de l'indice i1+t1                 */
/* t   : Le tableau d'entiers contenant              */
/*       les deux sous-tableaux contigus             */
/* i1  : L'indice dans t du premier entier           */
/*       du premier sous-tableau                     */
/* t1  : Le nombre d'entiers du premier sous-tableau */
/* t2  : Le nombre d'entiers du second sous-tableau  */

  static void fusion(int [] t,int i1,int t1,int t2) {
    int deb = i1;
    int i2 = i1+t1;
    int l = t1+t2;
    int l1 = i1+t1;
    int l2 = l1+t2;
    int [] tf = new int[l];
    for ( int i = 0 ; i < l ; i++ ) {
      if ( i1 == l1 ) {
        tf[i] = t[i2];
        i2++; }
        else {
        if ( i2 == l2 ) {
          tf[i] = t[i1];
          i1++; }
          else {
          if ( t[i1] < t[i2] ) {
            tf[i] = t[i1];
            i1++; }
            else {
            tf[i] = t[i2];
            i2++; } } } }
    for ( int i = 0 ; i < l ; i++ ) {
      t[deb+i] = tf[i]; }
  }

/* Fonction de tri par fusion                        */
/* par ordre croissant d'un tableau d'entiers        */
/* des indices indi a indf compris                   */
/* t    : Le tableau d'int à trier                   */
/*        par ordre croissant                        */
/* indi : L'indice initial des valeurs à trier       */
/* indf : L'indice final des valeurs à trier         */

  static void triFusion(int [] t,int indi,int indf) {
    int nbVal = indf-indi+1;
    if ( nbVal > 1 ) {
      if ( nbVal == 2 ) {
        if ( t[indf] < t[indi] ) {
          int aux = t[indi];
          t[indi] = t[indf];
          t[indf] = aux; } }
        else {
        int iMedian =(indi+indf)/2;
        triFusion(t,indi,iMedian);
        triFusion(t,iMedian+1,indf);
        fusion(t,indi,iMedian-indi+1,indf-iMedian); } }
  }

/* Fonction de tri par fusion                        */
/* par ordre croissant d'un tableau d'int            */
/* t : Le tableau d'int à trier                      */
/*     par ordre croissant                           */

  static void triFusion(int [] t) {
    triFusion(t,0,t.length-1);
  }

///////////////////////////////////////////////////////
  
/* Programme principal                               */

  public static void main(String [] args) {
    int [] t = initRand();
    Ecran.afficherln("Tableau initial");
    affichageTableau(t);
    triFusion(t);
    Ecran.afficherln("Tableau trié");
    affichageTableau(t);
    Ecran.sautDeLigne();
    Ecran.afficherln("Génération d'un tableau de 100000 valeurs");
    t = initRand(111,100000,100000000);
    Ecran.afficherln("Ce tableau est trié  : ",estTrie(t));
    Ecran.afficherln("Somme de ses valeurs : ",somme(t));
    triFusion(t);
    Ecran.afficherln("Réalisation du tri");
    Ecran.afficherln("Ce tableau est trié  : ",estTrie(t));
    Ecran.afficherln("Somme de ses valeurs : ",somme(t));
  }
}