import java.util.*;

class MergeSort2
// Destructive merge sort on a given array of Strings
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] a = line.split(" ");
  System.out.println("The words 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(String[] a)
 // Sort the contents of array a in ascending alphabetical order
 {
  if(a.length>1)
     {
      int i,mid = a.length/2;
      String[] half1 = new String[mid];
      String[] half2 = new String[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];
     }
 }

}