import java.util.*;

class MergeSort5
// Destructive merge sort on a random array of integers
// Timed but not printed
{
 public static void main(String[] args) throws Exception
 {
  Random rand = new Random();
  long time1,time2;
  Scanner input = new Scanner(System.in);
  System.out.print("Enter the number of numbers: ");
  int num = input.nextInt();
  System.out.print("Enter the highest number: ");
  int high = input.nextInt();
  Integer[] a = new Integer[num];
  for(int i=0; i<a.length; i++)
      a[i]= rand.nextInt(high);
  time1 = new Date().getTime(); 
  sort(a);
  time2 = new Date().getTime();
  System.out.println("Time taken to sort: "+(time2-time1)+"ms");
 }

 public static void sort(Integer[] a)
 // Sort the contents of array a in ascending numerical order
 {
  if(a.length>1)
     {
      int i,mid = a.length/2;
      Integer[] half1 = new Integer[mid];
      Integer[] half2 = new Integer[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].compareTo(half2[k])<0)
            {
             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];
     }
 }

}