/**
 * Implementation of the merge sort algorithm.
 * @author Jeff Raab
 */
public class MergeSort implements ISort {

    /** Returns the name of this sort algorithm. */
    public String getName() {
        return "Merge Sort";
    }
    
    /**
     * Performs the merge sort algorithm 
     * on the given array of objects.
     * @param anArray array of objects to sort
     */
    public void sort(Comparable[] anArray) {
        if (anArray == null) {
            return;
        }
        
        Comparable[] copy = new Comparable[anArray.length];
        for (int i = 0; i < copy.length; i++) {
            copy[i] = anArray[i];
        }
        
        sort(copy, 0, anArray.length, anArray);

        for (int i = 0; i < copy.length; i++) {
            anArray[i] = copy[i];
        }
    }

    /**
     * Performs the merge sort algorithm
     * on the given array of objects in the range [min, max).
     * @param anArray array of objects to sort
     * @param min minimum index in range to sort
     * @param max maximum index (exclusive) in range to sort
     * @param destArray destination array for objects to sort
     */
    public void sort(
        Comparable[] anArray, 
        int min, 
        int max, 
        Comparable[] destArray) 
    {
        if (max - min < 2) {
            return;
        }
        
        int mid = (min + max) / 2;
        
        sort(destArray, min, mid, anArray);
        sort(destArray, mid, max, anArray);
        
        merge(destArray, min, mid, max, anArray);
    }
    
    /**
     * Merges the sorted ranges [min, mid) and [mid, max)
     * in the given array of objects into one sorted range: [min, max).
     * @param anArray array of objects to sort
     * @param min minimum index in first range to merge
     * @param mid midpoint index in overall range to merge
     * @param max maximum index (exclusive) in second range to merge
     * @param destArray destination array for sorted objects
     */
    public void merge(
        Comparable[] anArray, 
        int min, 
        int mid, 
        int max,
        Comparable[] destArray) 
    {
        int i = min;
        int j = mid;
        int k = min;
        
        // choose smaller object of the smallest in the two ranges
        while ((i < mid) && (j < max)) {
            if (anArray[i].compareTo(anArray[j]) < 0) {
                destArray[k++] = anArray[i++];
            }
            else {
                destArray[k++] = anArray[j++];
            }
        }
        
        // copy remaining objects from the first range
        while (i < mid) {
            destArray[k++] = anArray[i++];
        }
        
        // copy remaining objects from the second range
        while (j < max) {
            destArray[k++] = anArray[j++];
        }
    }
}