class MergeSort
{
   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)
   {
      int[] folge = {13,4,15,3,16,12,2,1,51,26,11};
      
      printArray(folge);

      int[] ergebnis = performMergeSort(folge);

      printArray(ergebnis);
   }
}