package program2;

import java.lang.reflect.Array;

/**
 * @author Evan Johnson
 */

public class MergeSort{

	/**
	 * wrapper for recursive merge sort
	 *
	 * @param array array to be sorted
	 */
	public static <E extends Comparable<E>> void mergeSort(E[] array){
		@SuppressWarnings("unchecked")
		E temp[] = (E[]) Array.newInstance(array.getClass().getComponentType(), (array.length));
		mergeSort(array, temp,  0,  array.length - 1);
	}

	/**
	 * recursive merge sort
	 *
	 * @param array array to be sorted
	 * @param temp temporary array
	 * @param firstIndex left index of array
	 * @param lastIndex right index of array
	 */
	private static <E extends Comparable<E>> void mergeSort(E[] array, E[] temp, int left, int right){
		//if array can be split, split and continue recursive calls
		if( left < right )
		{
			int center = (left + right) / 2;
			mergeSort(array, temp, left, center);
			mergeSort(array, temp, center + 1, right);
			merge(array, temp, left, center, center + 1, right);
		}
	}

	/**
	 * merges two sorted arrays
	 *
	 * @param array containing two sub arrays to be merged
	 * @param temp temporary array for sorting values
	 * @param leftStart left index of left array
	 * @param leftEnd right index of left array
	 * @param rightStart left index of right array
	 * @param rightEnd right index of right array
	 */
    private static <E extends Comparable<E>> void merge(E[] array, E[] temp, int left, int leftEnd, int right, int rightEnd ){
        int index = left;
        int length = rightEnd - left + 1;

        //add elements into temp array in ascending order
        while(left <= leftEnd && right <= rightEnd)
            if(array[left].compareTo(array[right]) <= 0)
                temp[index++] = array[left++];
            else
                temp[index++] = array[right++];

        //copy remaining elements from left array
        while(left <= leftEnd)
            temp[index++] = array[left++];

        //copy remaining elements from right array
        while(right <= rightEnd)
            temp[index++] = array[right++];

        //copy temp back to the array
        for(int i = 0; i < length; i++, rightEnd--)
        	array[rightEnd] = temp[rightEnd];
    }
 }