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

class SortIntArrayRec3
{

 public static void main(String[] args)
 throws IOException
 // Illustrates using merge sort to sort an array of integers.
 // Generates random numbers to sort to allow sorting a large array
 // array not displayed.
 {
  int n;
  int[] array;
  Random rand = new Random();
  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++)
     array[i] = rand.nextInt();
  sort(array);
  System.out.println("The array is now sorted");
 }

 public static void sort(int[] a)
 // Sort the contents of array a in ascending numerical order
 {
  if(a.length>1)
     {
      int i,mid = a.length/2;
      int[] half1 = new int[mid];
      int[] half2 = new int[a.length-mid];
      for(i=0; i<mid; i++)
         half1[i]=a[i];
      for(; i<a.length; i++)
         half2[i-mid]=a[i];
      sort(half1);
      sort(half2);
      int j=0, k=0;
      for(i=0; j<half1.length&&k<half2.length; i++)
         if(half1[j]<half2[k])
            {
             a[i]=half1[j];
             j++;
            }
         else
            {
             a[i]=half2[k];
             k++;
            }
      for(; j<half1.length; i++, j++)
         a[i]=half1[j];
      for(; k<half2.length; i++, k++)
         a[i]=half2[k];
     }
 }

}