import java.util.Random;
class MergeSortRand
{
   static int[] performMergeSort(int[] f)
   {
      //Array fuer sortierte Folge
      int[] g;

      //testen of rekursiver Aufruf noetig
      if(f.length == 1) {
         g = new int[f.length];
         g[0] = f[0];
         return g;
      }
      else {
         //Index bestimmen, an dem f geteilt werden soll
         int t = (f.length-1)/2;

         //Arrays für linke und rechte Haelfte von f anlegen
         int[] lh = new int[t+1];
         int[] rh = new int[f.length - (t+1)]; 

         //Elemente aus f kopieren
         for(int i = 0; i < t+1; i++)        {lh[i] = f[i];}
         for(int i = t+1; i < f.length; i++) {rh[i-(t+1)] = f[i];}

         //linke und rechte Haelfte rekursiv sortieren
         lh = performMergeSort(lh);
         rh = performMergeSort(rh);

         //linke und rechte Haelfte mischen
         g = mergeArrays(lh,rh);
      }

      return g;
   }

   static int[] mergeArrays(int[] e, int[] f)
   {
      //neues Array fuer Ergebnis anlegen
      int[] g = new int[e.length + f.length];

      //Zum Merken der aktuellen Position in e und f
      int inde = 0;
      int indf = 0;

      //Fuellen des Arrays g
      for(int i = 0; i < (e.length + f.length); i++) {
         //Test, ob der naechste Eintrag in g aus e oder f kommt
         if((inde >= e.length) || ((indf < f.length) && (e[inde] > f[indf]))) {
            g[i] = f[indf];
            indf++;
         } 
         else {
            g[i] = e[inde];
            inde++;
         }
      }  

      return g;
   }

   static void printArray(int[] a) {
      for(int i = 0; i < a.length; i++) {
         System.out.print(a[i] + " ");
      }
      System.out.print("\n");
   }

   public static void main(String[] args)
   {
       System.out.println("Max  " + Runtime.getRuntime().maxMemory()/(1024*1024) +"MB");
       System.out.println("total " + Runtime.getRuntime().totalMemory()/(1024*1024)+"MB");
       System.out.println("free " + Runtime.getRuntime().freeMemory()/(1024*1024)+"MB");
       if (args.length<1) {
           System.out.println("you should add a integer parameter");
           return;
       }
       //variable defination
       int n = 0;
       try {
           n = Integer.parseInt(args[0]);
       } catch (NumberFormatException e){
           System.out.println("please input a integer value");
           return;
       }

       System.out.println("Sorting "+n+" Elements");
       int []folge = new int[n];
       
       Random rand = new Random();
       for(int i = 0; i < n; i++) {
           folge[i] = rand.nextInt(n);
       }
       
       //      printArray(folge);
      int[] ergebnis = performMergeSort(folge);
      //       System.out.println("Max  " + Runtime.getRuntime().maxMemory()/(1024*1024) +"MB");
      // System.out.println("total " + Runtime.getRuntime().totalMemory()/(1024*1024)+"MB");
      // System.out.println("free " + Runtime.getRuntime().freeMemory()/(1024*1024)+"MB");

      //      printArray(ergebnis);
   }
}