package sort;

/**
 * Merge Sort Algorithm
 * @author Winston Prakash
 */
public class MergeSort<E extends Comparable<E>> {
    private transient E[] dataArray;
    private transient E[] sortedArray;
    int dataSize;
    /** Creates a new instance of MergeSort */
    public MergeSort(E[] data) {
        dataArray = data;
        sortedArray = (E[]) new Comparable[data.length];
        System.arraycopy(data, 0, sortedArray, 0, data.length);
        dataSize = sortedArray.length;
    }
    
    public void sort(){
        recursiveMergeSort(0, dataSize - 1);
    }
    
    /**
     * Divide the array and recursively sort it. Them merge the two 
     * separately sorted array. Division stops only one data left
     * in the divided array, which is sorted by itself
     * 
     */
    private void recursiveMergeSort(int lowerBound, int upperBound){
        if (upperBound == lowerBound){
            return;
        }else{
            int midIndex = (lowerBound + upperBound)/2;
            recursiveMergeSort(lowerBound, midIndex);
            recursiveMergeSort(midIndex + 1, upperBound);
            merge(lowerBound, midIndex + 1, upperBound);
        }
    }
    
    /*
     * Merge the arrays, keep a pointer at the two arrays and move them when the 
     * next lowest in the array is added to the temporary array   
     */
    private void merge(int lowPointer, int highPointer, int upperBound) {
        int lowerBound = lowPointer;
        int sortedIndex = 0;
        int mid = highPointer - 1;
        int mergeBound = upperBound - lowerBound + 1;
        E[] tmpArray = (E[]) new Comparable[mergeBound];
        while ((lowPointer <= mid ) && (highPointer <= upperBound)){
            if (sortedArray[lowPointer].compareTo(sortedArray[highPointer]) < 0){
                tmpArray[sortedIndex++] = sortedArray[lowPointer++];
            }else{
                tmpArray[sortedIndex++] = sortedArray[highPointer++];
            }
        }
        while (lowPointer <= mid){
            tmpArray[sortedIndex++] = sortedArray[lowPointer++];
        }
        while (highPointer <= upperBound){
            tmpArray[sortedIndex++] = sortedArray[highPointer++];
        }
        for (int i = 0; i< mergeBound; i++){
            sortedArray[lowerBound + i] = tmpArray[i];
        }
    }
    
    public void displayData(){
        System.out.println("\nArray sorting using Merge Sort Algorithm");
        System.out.println("\nUnsorted Array");
        for (int i =0; i< dataArray.length; i++){
            System.out.print(dataArray[i] + "  ");
        }
        System.out.println("\nSorted Array");
        for (int i =0; i< sortedArray.length; i++){
            System.out.print(sortedArray[i] + "  ");
        }
        System.out.println();
    }
}