import java.util.*;

class MergeSort1
// Destructive merge sort on a given array of integers
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some numbers (all on one line):");
  String line = input.nextLine();
  String[] numbers = line.split(" ");
  Integer[] a = new Integer[numbers.length];
  for(int i=0; i<a.length; i++)
      a[i]=new Integer(numbers[i]);
  System.out.println("The numbers are stored in an array as:");
  System.out.println(Arrays.toString(a));
  sort(a);
  System.out.println("After sorting the array is:");
  System.out.println(Arrays.toString(a));
 }

 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];
     }
 }

}