import java.util.*;

class MergeSort7
// Destructive merge sort on a random ArrayList of integers
{
 public static void main(String[] args) throws Exception
 {
  Random rand = new Random();
  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();
  ArrayList<Integer> a = new ArrayList<Integer>();
  for(int i=0; i<num; i++)
      a.add(rand.nextInt(high));
  System.out.println("The numbers are stored in an ArrayList as:");
  System.out.println(a);
  sort(a);
  System.out.println("After sorting the ArrayList is:");
  System.out.println(a);
 }

 public static void sort(ArrayList<Integer> a)
 // Sort the contents of ArrayList a in ascending numerical order
 {
  if(a.size()>1)
     {
      int i,mid = a.size()/2;
      ArrayList<Integer> half1 = new ArrayList<Integer>();
      ArrayList<Integer> half2 = new ArrayList<Integer>();
      for(i=0; i<mid; i++)
         half1.add(a.get(i));
      for(; i<a.size(); i++)
         half2.add(a.get(i));
      sort(half1);
      sort(half2);
      int j=0, k=0;
      for(i=0; j<half1.size()&&k<half2.size(); i++)
         if(half1.get(j).compareTo(half2.get(k))<0)
            {
             a.set(i,half1.get(j));
             j++;
            }
         else
            {
             a.set(i,half2.get(k));
             k++;
            }
      for(; j<half1.size(); i++, j++)
         a.set(i,half1.get(j));
      for(; k<half2.size(); i++, k++)
         a.set(i,half2.get(k));
     }
 }



}