import java.io.*;
import java.lang.*;
import java.util.*;

class TriRec {

  final static int N = 10;
  static int[] a = new int[N];          // \esc{Le tableau à trier} 

  static void Initialisation() { // \esc{On tire au sort des nombres} 
                                    // \esc{entre 0 et 127, en initialisant} 
                                    // \esc{le tirage au sort sur l'heure} 
      for (int i = 0; i < N; ++i)
          a[i] = (int) (Math.random() * 128);
  }

  static void Impression() {
      for (int i = 0; i < N; ++i)
          System.out.print (" " + a[i] + " ");
      System.out.println ("");
  }

  static void QSort(int g, int d)  {
  // \esc{QuickSort, voir page \pageref{prog:qsort}} 
  
    int i, m, x, v;

    if (g < d) {
        v = a[g];
        m = g;
        for (i = g+1; i <= d; ++i)
            if (a[i] < v) {
                ++m;
                x = a[m]; a[m] = a[i]; a[i] = x; // \esc{Echanger $a_m$ et $a_i$}
            }
        x = a[m]; a[m] = a[g]; a[g] = x;         // \esc{Echanger $a_m$ et $a_g$}
        QSort (g, m-1);
        QSort (m+1, d);
    }
  }

  static void QuickSort(int g, int d) {
  // \esc{Quicksort, voir page \pageref{prog:quicksort}} */
  
    int v,t,i,j;

    if (g < d) {
        v = a[d]; i= g-1; j = d;
        do {
            do 
                ++i; 
            while (a[i] < v);
            do 
                --j; 
            while (a[j] > v);
            t = a[i]; a[i] = a[j]; a[j] = t;
        } while (j > i);
        a[j] = a[i]; a[i] = a[d]; a[d] = t;
        QuickSort (g, i-1);
        QuickSort (i+1, d);
    }
  }

  static int[] b = new int[N];

  static void TriFusion(int g, int d)   {
  // \esc{Tri par fusion, voir page \pageref{prog:tri-fusion}} */

    int   i, j, k, m;

    if (g < d) {
        m = (g + d) / 2;
        TriFusion (g, m);
        TriFusion (m + 1, d);
        for (i = m; i >= g; --i)
             b[i] = a[i];
        for (j = m+1; j <= d; ++j)
             b[d+m+1-j] = a[j];
        i = g; j = d;
        for (k = g; k <= d; ++k)
            if (b[i] < b[j]) {
                a[k] = b[i]; ++i;
            } else {
                a[k] = b[j]; --j;
            }
    }
  }

  public static void main(String args[]) {

      Initialisation();   // \esc{On lit le tableau}

      Impression();       // \esc{et on l'imprime}
      QSort(0,N-1);       // \esc{On trie}
      Impression();       // \esc{On imprime le résultat} 
      QuickSort(0,N-1);      
      Impression();    
      TriFusion(0,N-1);
      Impression();    
  }
}