/**
    FILE:           MergeSort.java
    AUTHOR:         Cheng, Jeff
    LAST CHANGE:    3-22-02
    Functions:      MergeSort()--------> creates an array, may be presorted.
                    createAndSort()--> creates an array and sorts the
                                       array, may print array after.
                    merge()----------> combine two *presorted* arrays.
                    print()----------> print the entire array.
                    sort()-----------> sort the array using merge sort;
                                       requires extra storage.     
                    
    COPYRIGHT:      You may use, modify, or distribute my code for 
                    non-commerical use only; you must cite me, Jeff Cheng, 
                    as the source. 
*/

package sorts;

class MergeSort{
    public static final int MAX_VALUE = 1000000;
    private int a[];
    
    public MergeSort(int arraySize, boolean presorted){
        a = new int[arraySize];
        
        if (presorted){
            //  sorted array
            for (int i=0; i < a.length; i++){
                a[i] = i;
            }
        }
        else {
            //  seed the array elements randomly
            for (int i=0; i < a.length; i++){
                a[i] = (int)(Math.random()*MAX_VALUE);   
            }
        }
    }
    
    public static void createAndSort(int arraySize, boolean presorted,
                                     boolean printIt){
        long timeBegan = 0;
        long timeFinished = 0; 
        long timeNeeded = 0;
        
        //  create an array of integers
        MergeSort aMergeSorter = new MergeSort(arraySize, presorted);

        //  time the sorting algorithm
        timeBegan = System.currentTimeMillis();
        
        aMergeSorter.sort();
        
        timeFinished = System.currentTimeMillis();
        timeNeeded = timeFinished - timeBegan;
        System.out.println("\t Sorting the array of size " + arraySize +
                            " took = " + timeNeeded + " milliseconds.");       
                            
        if (printIt){
            System.out.println("\n\t Now print the array elements:\n" +
                               "\t Note if the array is too large, " +
                               "the elements may run off the screen!\n");
            aMergeSorter.print();
        }
    }
    
  public void print(){
    for (int i = 0; i < a.length;i++){
        System.out.println(" a[" + i + "] = " + a[i] + "\n");
        }
 }
 
  public void sort(int a[], int low, int high) {
    int mid = (low + high) /2;
    
    if (low < high){
        sort(a, low, mid);  //  sort the lower half
        sort(a, mid+1, high);   //  sort the higher half
        merge(a, low, mid, high);
    }
    }
 
 public void sort(){    //  used to hide call arguments in createAndSort()
    sort(a, 0, a.length-1);}
    
 public void merge(int a[], int low, int mid, int high){
    int scratchArray[] = new int[a.length];
    int lowRegionIndex = low;   //  first small element in array
    int highRegionIndex = mid + 1;  //  first large element in array
    int scratchArrayIndex = 0;
 
    //  while we still have two subarrays/sublists
    while ((lowRegionIndex <= mid)&&(highRegionIndex <= high)){
        //  if-else compares the two regions and decides which
        //  element should be copied to the current index in
        //  the scratch array.
        if (a[lowRegionIndex] < a[highRegionIndex]){
            scratchArray[scratchArrayIndex] = a[lowRegionIndex];      
            lowRegionIndex++;
            scratchArrayIndex++;
            }
        else{   //  a[lowRegionIndex] >= a[highRegionIndex]
            scratchArray[scratchArrayIndex] = a[highRegionIndex];
            highRegionIndex++;
            scratchArrayIndex++;
            }
    }
    
    //  now we have exhausted one of the sublists
    //  let's copy the leftover elements in
    //  the remaining list to the scratch array.
    //  Note that only 1 while gets executed.
    while (lowRegionIndex <= mid){
        scratchArray[scratchArrayIndex] = a[lowRegionIndex];
        lowRegionIndex++;
        scratchArrayIndex++;
        }
 
    while (highRegionIndex <= high){
        scratchArray[scratchArrayIndex] = a[highRegionIndex];
        highRegionIndex++;
        scratchArrayIndex++;
        }
    
    scratchArrayIndex = 0;  //  reset it for copying
    
    //  now copy the scratch array back to a[]
    for (int i = low; i <= high; i++){
        a[i] = scratchArray[scratchArrayIndex];
        scratchArrayIndex++;
        }
    }   
}