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

import java.util.Random;

public class TriFusion {

  static long somme(int [] t) {
    long total = 0L;
    int i;
    for ( i = 0 ; i < t.length ; i = i+1 ) {
      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 = i+1; }
    return trie;
  }

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

/* Methode 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];
    int i;
    t[0] =(int) (r.nextDouble()*10.0);
    for ( i = 1 ; i < t.length ; i = i+1 ) {
      t[i] = t[i-1] + (int) (r.nextDouble()*10.0); }
    return t;
  }

/* Methode 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);
    int i;
    t[deb] =(int) (r.nextDouble()*fact);
    for ( i = 1 ; i < n ; i = i+1 ) {
      t[i+deb] = t[i+deb-1] + (int) (r.nextDouble()*fact); }
  }

/* Methode 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;
    int i;
    int nb = 10;
    int i1;
    int i2;
    int aux;
    t = initRandCroissant(n,seed);
    for ( i = 0 ; i < nb ; i = i+1 ) {
      i1 =(int) (r.nextDouble()*(n+1));
      i2 =(int) (r.nextDouble()*(n+1));
      aux = t[i1];
      t[i1] = t[i2];
      t[i2] = aux; }
    return t;
  }

/* Methode de creation d'un tableau de 10 int    */
/* initialise avec des valeurs tirees au sort    */
/* entre 0 et 1000 inclus                        */
  
  static int [] initRand() {
    int [] t = new int[10000000];
    int i;
    for ( i = 0 ; i < t.length ; i = i+1 ) {
      t[i] =(int) (Math.random()*1001.0); }
    return t;
  }

///////////////////////////////////////////////////
  
/* Methode de fusion en un tableau trie          */
/* de deux sous-tableaux contigus                */
/* d'un tableau d'entiers                        */
/* Sous-tableau 1: t1 valeurs depuis l'indice i1 */
/* Sous-tableau 2: t2 valeurs au dela            */

  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];
    int i;
    for ( i = 0 ; i < l ; i = i+1 ) {
      if ( i1 == l1 ) {
        tf[i] = t[i2];
        i2 = i2+1; }
        else {
        if ( i2 == l2 ) {
          tf[i] = t[i1];
          i1 = i1+1; }
          else {
          if ( t[i1] < t[i2] ) {
            tf[i] = t[i1];
            i1 = i1+1; }
            else {
            tf[i] = t[i2];
            i2 = i2+1; } } } }
    for ( i = 0 ; i < l ; i = i+1 ) {
      t[deb+i] = tf[i]; }
  }

/* Methode de tri par fusion  d'un tableau       */
/* d'entiers des indices indi a indf compris     */

  static void triFusion(int [] t,int indi,int indf) {
    int iMedian;
    int aux;
    switch ( indf-indi ) {
      case 0 :
        break;
      case 1 : {
        if ( t[indf] < t[indi] ) {
           aux = t[indi];
          t[indi] = t[indf];
          t[indf] = aux; } }
        break;
      default : {
        iMedian =(indi+indf)/2;
        triFusion(t,indi,iMedian);
        triFusion(t,iMedian+1,indf);
        fusion(t,indi,iMedian-indi+1,indf-iMedian); } }
  }

/* Methode de tri par fusion de l'ensemble       */
/* d'un tableau d'entiers                        */

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

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

  public static void main(String [] args) {
    int [] t;
    t = initRand();
    Ecran.afficherln(estTrie(t)," ",somme(t));
    //affichageTableau(t);
    triFusion(t);
    //affichageTableau(t);
    Ecran.afficherln(estTrie(t)," ",somme(t));
  }
}