/* Auteur: Nicolas JANEY          */
/* nicolas.janey@univ-fcomte.fr   */
/* Avril 2005                     */

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

public class TriRecursifFonction {
  static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
  
  /* Fonction de fusion de deux tableaux d'entiers tries  */
  /* en un tableau d'entiers tries                        */
  /* t1,t2 : tableaux d'entiers tries                     */
  /* Resultat fonction : Tableau d'entiers trie           */

  public static int [] fusion(int [] t1,int [] t2) {
  /* Calcul des tailles des tableau t1 et t2              */
    int n1 = t1.length;
    int n2 = t2.length;
  /* Creation d'un tableau de taille suffisante           */
  /* pour contenir toutes les valeurs de t1 et t2 :       */
  /* (n1+n2) valeurs                                      */
    int [] t = new int[n1+n2];
  /* Définition et initialisation a 0 de deux variables   */
  /* compteur (i1 et i2) pour stocker le nombre           */
  /* de valeurs de t1 et le nombre de valeurs de t2       */
  /* qui ont deja ete placees dans t                      */
    int i1 = 0;
    int i2 = 0;
  /* Pour les n1+n2 valeurs a placer dans t               */
    for ( int i = 0 ; i < n1+n2 ; i++ ) {
  /* Si toutes les valeurs de t1 sont deja dans t,        */
  /* la valeur a placer dans t est la premiere valeur     */
  /* de t2 non encore placee dans t                       */
      if ( i1 == n1 ) {
        t[i] = t2[i2];
        i2++; }
        else
  /* Sinon, si toutes les valeurs de t2 sont deja dans t, */
  /* la valeur a placer dans t est la premiere valeur     */
  /* de t1 non encore placee dans t                       */
        if ( i2 == n2 ) {
          t[i] = t1[i1];
          i1++; }
          else
  /* Sinon, si la premiere valeur de t1 non placee dans t */
  /* est plus petite que la premiere valeur de t2         */
  /* non placee dans t, alors c'est la valeur de t1       */
  /* qui va dans t                                        */
          if ( t1[i1] < t2[i2] ) {
            t[i] = t1[i1];
            i1++; }
            else {
  /* Sinon, c'est la valeur de t2 qui va dans t           */
            t[i] = t2[i2];
            i2++; } }
  /* Resultat fonction : le tableau t ainsi cree          */
  /* et rempli                                            */
    return(t);
  }
  
  /* Fonction de creation d'un tableau d'entiers          */
  /* tires au hasard                                      */
  /* taille : nombre d'entiers du tableau                 */
  /* max    : valeur maximale des entiers tires au sort   */
  
  public static int [] initTableau(int taille,int max) {
    int [] t = new int[taille];
    for ( int i = 0 ; i < t.length ; i++ )
      t[i] =(int) (Math.random()*(max+1));
    return(t);
  }

  /* Fonction d'affichage d'un tableau d'entiers          */
  /* t : tableau dont les valeurs doivent etre affichees  */
  
  public static void afficheTableau(int [] t) {
    int i;
    for ( i = 0 ; i < t.length ; i++ )
      System.out.print(t[i]+" ");
    System.out.println();
  }
  
  /* Fonction de d'extraction d'un sous-tableau           */
  /* d'un tableau                                         */
  /* t : tableau ou l'extraction est faite                */
  /* indi : indice du premier element extrait             */
  /* indf : indice du dernier element extrait             */
  /* Resultat fonction : tableau extrait                  */

  public static int [] sousTableau(int [] t,int indi,int indf) {
  /* Calcul du nombre d'entiers a extraire                */
    int nb = indf-indi+1;
  /* Declaration et allocation du tableau resultat        */
    int [] st = new int[nb];
  /* Recopie des nb entiers extraits de t vers s          */
    for ( int i = 0 ; i < nb ; i++ )
      st[i] = t[indi+i];
  /* Resultat fonction : Tableau extrait                  */
    return(st);
  }
  
  /* Fonction de tri d'un tableau d'entiers               */
  /* t : tableau qui doit etre trie                       */
  /* Resultat fonction : tableau trie                     */

  public static int [] triRecursif(int [] t) {
  /* Declaration et allocation du tableau resultat        */
  /* avec la taille du tableau en parametre               */
    int r [] = new int[t.length];
  /* Si t n'a qu'un seul element, il est recopie dans r   */
  /* et r est retourne                                    */
    if ( t.length == 1 ) {
      r[0] = t[0];
      return(r); }
  /* Si t a deux elements, ils sont recopies dans r       */
  /* avec le plus petit a l'indice 0 et le plus grand     */
  /* a l'indice 1 et r est retourne                       */
    if ( t.length == 2 ) {
      if ( t[0] < t[1] ) {
        r[0] = t[0];
        r[1] = t[1]; }
        else  {
        r[0] = t[1];
        r[1] = t[0]; }
      return(r); }
  /* t possede au moins trois elements                    */
  /* Calcul de l'indice de l'element du milieu de t       */
    int ind = (t.length-1)/2;
  /* Creation du sous-tableau de t des indices 0 a ind    */
    int [] t1 = sousTableau(t,0,ind);
  /* Creation du tableau trie des elements de t1          */
  /* par appel recursif                                   */
    int [] tt1 = triRecursif(t1);
  /* Creation du sous-tableau de t des indices ind+1      */
  /* a t.length-1                                         */
    int [] t2 = sousTableau(t,ind+1,t.length-1); 
  /* Creation du tableau trie des elements de t2          */
  /* par appel recursif                                   */
    int [] tt2 = triRecursif(t2);
  /* Creation du resultat de la fonction par appel        */
  /* a la fusion de deux tableaux tries                   */
  /* en un tableau trie                                   */
    return(fusion(tt1,tt2));
  }
  
  /* Fonction principale                                  */
  
  public static void main(String [] args) throws IOException {
  /* Lecture au clavier des donnees initiales             */
    System.out.print("Taille du tableau a generer et a trier : ");
    int n = Integer.valueOf(flux.readLine()).intValue();
    System.out.print("Valeur maximale des entiers du tableau : ");
    int max = Integer.valueOf(flux.readLine()).intValue();
  /* Generation du tableau a trier tire au hasard         */
    int [] t = initTableau(n,max);
  /* Affichage du tableau non trie                        */
    System.out.println("Tableau initial :");
    afficheTableau(t);
  /* Determination de l'heure de debut de tri             */
  /* (millisecondes depuis le 01/01/1970 à 0h 0mn 0s      */
    long debut = (new Date()).getTime();
  /* Tri du tableau                                       */
    int [] tt = triRecursif(t);
  /* Determination de l'heure de fin de tri               */
    long fin = (new Date()).getTime();
  /* Affichage du tableau trie                            */
    System.out.println("Tableau trie :");
    afficheTableau(tt);
  /* Affichage du temps d'execution du tri                */
  /* (en millisecondes)                                   */
    System.out.println("Temps ecoule :");
    System.out.println(fin-debut);
  }
}