import java.util.*;
/** 
 * Merge sort routine for arrays
 * @author Suzanne Balik, 6 Nov 2001
 * MODIFICATION: Changed to make sort "stable" SPB, 30 Nov 2002
 * POST: Array is in sorted (non-decreasing) order
 */
public class MergeSort {

  public static void sort(int[] array) {
  
    //Copy sorted array to original array when merge sort is complete
    System.arraycopy
      (mergeSort(array, 0, array.length - 1), 0, array, 0, 
                 array.length);
    
  }
  
  private static int[] mergeSort(int[] array, int first, int last) {
    
    int [] newArray;
    if (first == last) {
      newArray = new int[1];
      newArray[0] = array[first];
    }
    else {
      int mid = (last - first) / 2 + first;
      
      int [] firstHalf = mergeSort(array, first, mid);
      
      int [] lastHalf = mergeSort(array, mid + 1, last);
  
     
      newArray = new int[last - first + 1];
      int i, j, k;
      for(i = 0, j = 0, k = 0; 
              i < newArray.length && j < firstHalf.length && 
	      k < lastHalf.length; i++) {
        if (firstHalf[j] <= lastHalf[k])
	  newArray[i] = firstHalf[j++];
	else
	  newArray[i] = lastHalf[k++];
      }
      if (j < firstHalf.length)
        for ( ; i < newArray.length; i++, j++)
	  newArray[i] = firstHalf[j];
      else
        for ( ; i < newArray.length; i++, k++)
	  newArray[i] = lastHalf[k];
    }
    //System.out.println(MergeSort.toString(newArray));	  
    return newArray;
  }
      
      
  
  
  public static String toString(int[] array) {
  
    String s = "[";
    for (int i = 0; i < array.length; i++)
      s += " " + array[i];
    s += " ]";
    return s;
  }
  
  public static void main(String[] args) {
  
    int[] array = {2, 8, 1, 4, 4, 5, 7, 6};
    
    System.out.println("Unsorted array: " +
                        MergeSort.toString(array));
    MergeSort.sort(array);
    System.out.println("Sorted array:   " + 
                        MergeSort.toString(array));
    if (args.length == 1) { 
      array = new int[Integer.parseInt(args[0])];
      Random generator = new Random();
      final int MAX = 200;
      for (int i = 0; i < array.length; i++)
        array[i] = generator.nextInt(MAX);
      long startTime = System.currentTimeMillis();
      MergeSort.sort(array);
      long stopTime = System.currentTimeMillis();
      System.out.println("Time to sort " + args[0] + 
                         " random integers in range 1 - 200: " + 
			 (stopTime - startTime) + "ms");
      
      // ADD CODE HERE TO CREATE AN ARRAY OF THE SAME SIZE
      // IN ASCENDING ORDER, eg., 1, 2, 3, 4, ...
      // AND SORT AND TIME IT
      
      
      // ADD CODE HERE TO CREATE AN ARRAY OF THE SAME SIZE
      // IN DESCENDING ORDER, eg., 2000, 1999, 1998, .....
      // AND SORT AND TIME IT
      
    }
  }
}