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

import java.util.Random;

public class TriRapide {

  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(long seed,int n,int max) {
    Random r = new Random(seed);
    int [] t = new int[n];
    int i;
    for ( i = 0 ; i < t.length ; i = i+1 ) {
      t[i] =(int) (r.nextDouble()*(max+1)); }
    return t;
  }

///////////////////////////////////////////////////

/* Methode de reorganisation d'un tableau t      */
/* d'entiers des indices indi a indf inclus      */
/* par replacage a gauche de toutes les valeurs  */
/* plus petites que t[pivot], a droite de toutes */
/* les valeurs plus grandes que t[pivot]         */
/* et au centre de toutes les valeurs egales     */
/* a t[pivot]                                    */
/* Retourne l'indice de la valeur d'indice       */
/* maximum, apres replacage, de toutes           */
/* les valeurs egales a t[pivot]                 */

  static int pivotage(int [] t,int indi,int indf,int pivot) {
    int aux;
    int i;
    int j;
    aux = t[pivot];
    t[pivot] = t[indf];
    t[indf] = aux;
    j = indi;
    for ( i = indi ; i < indf ; i = i+1 ) {
      if ( t[i] <= t[indf] ) {
        if ( i != j ) {
          aux = t[i];
          t[i] = t[j];
          t[j] = aux; }
        j = j+1; } }
    if ( indf != j ) {
      aux = t[indf];
      t[indf] = t[j];
      t[j] = aux; }
    return j;
  }

/* Methode de tri par QuickSort d'un tableau     */
/* d'entiers des indices indi a indf compris     */
/* Pivot choisi a la valeur moyenne des valeurs  */
/* min et max                                    */

  static void triRapide(int [] t,int indi,int indf) {
    int iMedian;
    int aux;
    int pivot;
    if ( indf == indi+1 ) {
      if ( t[indf] < t[indi] ) {
        aux = t[indi];
        t[indi] = t[indf];
        t[indf] = aux; } }
      else {
      pivot = (indi+indf)>>1;
      iMedian = pivotage(t,indi,indf,pivot);
      if ( iMedian > indi+1 ) {
        triRapide(t,indi,iMedian-1); }
      if ( iMedian < indf-1 ) {
        triRapide(t,iMedian+1,indf); } }
  }

/* Methode de tri par QuickSort                  */
/* de l'ensemble d'un tableau d'entiers          */
/* Pivot choisi a la valeur moyenne des valeurs  */
/* min et max du tableau                         */

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

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

  public static void main(String [] args) {
/*    for ( int p = 0 ; p < 13 ; p++ ) {
      int [] t;
      t = initRand(11,13);
      affichageTableau(t);
      Ecran.afficherln(reorganisation(t,t[p],0,t.length-1));
      affichageTableau(t); }*/
    int [] t;
    t = initRand(111,20000,100000000);
    Ecran.afficherln(estTrie(t)," ",somme(t));
    //affichageTableau(t);
    triRapide(t);
    //Ecran.afficherln(pivotage(t,0,t.length-1,6));
    //affichageTableau(t);
    Ecran.afficherln(estTrie(t)," ",somme(t)); 
  }
}