import java.io.*;
class SortIntArrayRec4
{

 public static void main(String[] args)
 throws IOException
 // Illustrates constructive merge sort to sort an array of integers
 {
  int n;
  int[] array, array1;
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  System.out.print("Enter number of integers : ");
  n = Integer.parseInt(in.readLine());
  array = new int[n];
  for(int i=0; i<n; i++)
     {
      System.out.print("Enter integer "+i+": ");
      array[i] = Integer.parseInt(in.readLine());
     }
  System.out.println("The array you entered is:");
  System.out.println(arrayToString(array));
  array1 = sort(array);
  System.out.println("After sorting, the array is:");
  System.out.println(arrayToString(array));
  System.out.println("The new array is:");
  System.out.println(arrayToString(array1));
 }

 private static String arrayToString(int[] a)
 {
  String str="[";
  if(a.length>0)
     {
      str+=a[0];
      for(int i=1; i<a.length; i++)
         str+="|"+a[i];
     }
  return str+"]";
 }

 public static int[] sort(int[] a)
 // Sort the contents of array a in ascending numerical order
 // and return in a new array
 {
  return sort(a,0,a.length);
 }

 private static int[] sort(int[] a,int from,int to)
 // Sort the contents of array a from position 'from' up to but
 // not including position 'to' in ascending numerical order
 // and return in a new array
 {
  if(to-from>1)
     {
      int i,mid = (from+to)/2;
      int[] half1=sort(a,from,mid);
      int[] half2=sort(a,mid,to);
      int j=0, k=0;
      int[] b = new int[to-from];
      for(i=0; j<half1.length&&k<half2.length; i++)
         if(half1[j]<half2[k])
            {
             b[i]=half1[j];
             j++;
            }
         else
            {
             b[i]=half2[k];
             k++;
            }
      for(; j<half1.length; i++, j++)
         b[i]=half1[j];
      for(; k<half2.length; i++, k++)
         b[i]=half2[k];
      return b;
     }
  else
     {
      int[] b = new int[1];
      b[0]=a[from];
      return b;
     }
 }

}