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

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

public class TriRecursifAction {
  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 void fusion(int [] t,int indi,int ind,int indf) {
  /* Calcul des tailles des zones de t a fusioner         */
    int n1 = ind-indi+1;
    int n2 = indf-ind;
  /* Creation d'un tableau de taille suffisante           */
  /* pour contenir toutes les valeurs des deux zones :    */
  /* (n1+n2) valeurs                                      */
  /* L'utilisation de ce tableau auxiliaire est           */
  /* necessaire pour eviter les risques d'ecrasement      */
  /* des valeurs du tableau t et par souci d'optimisation */
    int [] nt = new int[n1+n2];
  /* Définition et initialisation a 0 de deux variables   */
  /* compteur (i1 et i2) pour stocker le nombre           */
  /* de valeurs de la zone 1 et le nombre de valeurs      */
  /* de la zone 2 qui ont deja ete placees dans nt        */
    int i1 = indi;
    int i2 = ind+1;
  /* Pour les n1+n2 valeurs a placer dans nt              */
    for ( int i = 0 ; i < n1+n2 ; i++ ) {
  /* Si toutes les valeurs de la zone 1 sont deja         */
  /* dans nt, la valeur a placer dans nt est              */
  /* la premiere valeur de la zone 2 non placee dans nt   */
      if ( i1 == ind+1 ) {
        nt[i] = t[i2];
        i2++; }
        else
  /* Sinon, si toutes les valeurs de t2 sont deja         */
  /* dans nt, la valeur a placer dans nt est              */
  /* la premiere valeur de la zone 1 non placee dans nt   */
        if ( i2 == indf+1 ) {
          nt[i] = t[i1];
          i1++; }
          else
  /* Sinon, si la premiere valeur de la zone 1 non placee */
  /* dans t est plus petite que la premiere valeur        */
  /* de la zone 2 non placee dans t,                      */
  /* alors c'est la valeur de zone 1 qui va dans nt       */
          if ( t[i1] < t[i2] ) {
            nt[i] = t[i1];
            i1++; }
            else {
  /* Sinon, c'est la valeur de la zone 2 qui va dans nt   */
            nt[i] = t[i2];
            i2++; } }
  /* Les valeurs du tableau nt sont replacee dans t       */
    for ( int i = 0 ; i < n1+n2 ; i++ )
      t[indi+i] = nt[i];
  }
  
  /* 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 tri d'une portion d'un tableau d'entiers */
  /* t : tableau dont une portion doit etre trie          */
  /* indi : indice du premier entier de la portion        */
  /*        a trier                                       */
  /* indf : indice du dernier entier de la portion        */
  /*        a trier                                       */

  public static void tri(int [] t,int indi,int indf) {
  /* Si la portion ne contient qu'un seul entier          */
  /* (indi egal a indf) -> elle est deja triee            */
    if ( indi == indf ) {
      return; }
  /* Si la portion ne contient que deux entiers           */
  /* (indf egal a indi+1) 
  /* -> soit elle est deja triee, soit les deux entiers   */
  /*    doivent etre permutes pour qu'elle le soit        */
    if ( indf == indi+1 ) {
      if ( t[indi] > t[indf] ) {
        int aux = t[indi]; 
        t[indi] = t[indf];
        t[indf] = aux; }
      return; }
  /* La portion a trier contient trois ou plus entiers    */
  /* Calcul de l'indice de l'entier intermediaire         */
  /* de la zone a trier                                   */
    int ind = indi+(indf-indi)/2;
  /* Tri de la premiere demi-zone                         */
    tri(t,indi,ind);
  /* Tri de la seconde demi-zone                          */
    tri(t,ind+1,indf);
  /* Fusion des deux demi-zones maintenant triees         */
  /* en une seule zone triee                              */
    fusion(t,indi,ind,indf);
  }

  /* Fonction de tri d'un tableau d'entiers               */
  /* t : tableau qui doit etre trie                       */

  public static void triRecursif(int [] t) {
  /* Appel a la fonction recursive pour les indices 0     */
  /* et t.length-1                                        */
    tri(t,0,t.length-1);
  }

  /* 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                                       */
    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(t);
  /* Affichage du temps d'execution du tri                */
  /* (en millisecondes)                                   */
    System.out.println("Temps ecoule :");
    System.out.println(fin-debut);
  }
}