public final class Merge {

   private static int [] temp;

   public static void merge_sort (int [] data, int n) {
      temp = new int [n];  // no use allocating it again and again
      merge_sort (data, 0, n);  // sort the whole array
   }

   // Sort the elements data[first..first+n-1]
   public static void merge_sort (int [] data, int first, int n) {
      System.out.printf ("number=%d; range=%d..%d:  ", n, first, first+n-1);
      System.out.println (java.util.Arrays.toString (data));
      if (n>1) {
         System.out.printf ("first=%d, n=%d: ", first, n); 
         printArray (data, first, n);

         final int n1 = n/2;
         final int n2 = n-n1;
         assert n1+n2==n;

         merge_sort (data, first, n1);    // Sort data[first..first+n1-1]
         merge_sort (data, first+n1, n2); // Sort data[first+n1..first+n-1]

         System.out.print ("after both recursive calls: ");
         printArray (data, first, n);

         merge (data, first, n1, n2);

         System.out.print ("after merge                 ");
         printArray (data, first, n);
      }
   }

   /*
     Merge data[first..first+n1-1] and  data[first+n1..first+n1+n2-1]
   */
   public static void merge (int [] data, int first, int n1, int n2) {
      int copiedTotal=0, copiedLeft=0, copiedRight=0;
      while ((copiedLeft<n1) && (copiedRight<n2)) {
         if (data[first+copiedLeft]<data[first+n1+copiedRight]) {
            temp[copiedTotal++] = data[first + (copiedLeft++)];
         } else {
            temp[copiedTotal++] = data[first + n1 + (copiedRight++)];
         }
      }
      
      while (copiedLeft  < n1)  temp[copiedTotal++] = data[first+(copiedLeft++)];
      while (copiedRight < n2)  temp[copiedTotal++] = data[first+n1+(copiedRight++)];
      assert copiedTotal == n1+n2;

      System.arraycopy (temp, 0, data, first, copiedTotal);
   }

   private static void printArray (int [] data, int n) {
      printArray (data, 0, n);
   }

   private static void printArray (int [] data, int first, int n) {
      System.out.print ("[");
      for (int i=first; i<first+n; i++) {
         System.out.print (data[i]);
         if (i<first+n-1) System.out.print (", ");
      }
      System.out.println ("]");
   }

   public static void main (final String [] args) {
      final int [] data  = new int [args.length];
      int n = 0;
      for (int i=0; i<args.length; i++) {
         try {
            data[n++] = Integer.parseInt(args[i]);
         } catch (NumberFormatException ex) {
            // ignore bad input
         }
      }
      printArray (data, n);
      merge_sort (data, n);
      printArray (data, n);
   }
}