/**
 * Implementation of the merge sort algorithm 
 * that splits data into 3, rather than 2 parts.
 * @author Jeff Raab
 */
public class MergeSort3 implements ISort {

    /** Returns the name of this sort algorithm. */
    public String getName() {
        return "Merge Sort 3-way";
    }
    
    /**
     * 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 mid1 = min + ((max - min) / 3);
        int mid2 = min + 2 * ((max - min) / 3) + 1;

        sort(destArray, min, mid1, anArray);
        sort(destArray, mid1, mid2, anArray);
        sort(destArray, mid2, max, anArray);
        
        merge(destArray, min, mid1, mid2, max, anArray);
    }
    
    /**
     * Merges the sorted ranges [min, mid1), [mid1, mid2) and [mid2, 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 mid1 first midpoint index in overall range to merge
     * @param mid2 second 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 mid1, 
        int mid2, 
        int max,
        Comparable[] destArray) 
    {
        int i = min;
        int j = mid1;
        int k = mid2;

        int l = min;
        
        // choose smaller object of the smallest in the three ranges
        while ((i < mid1) && (j < mid2) && (k < max)) {
            if (anArray[i].compareTo(anArray[j]) < 0) {
                if (anArray[i].compareTo(anArray[k]) < 0) {
                    destArray[l++] = anArray[i++];
                }
                else {
                    destArray[l++] = anArray[k++];
                }
            }
            else {
                if (anArray[j].compareTo(anArray[k]) < 0) {
                    destArray[l++] = anArray[j++];
                }
                else {
                    destArray[l++] = anArray[k++];
                }
            }
        }
            
        // case where first and second ranges have remaining objects
        while ((i < mid1) && (j < mid2)) {
            if (anArray[i].compareTo(anArray[j]) < 0) {
                destArray[l++] = anArray[i++];
            }
            else {
                destArray[l++] = anArray[j++];
            }
        }

        // case where second and third ranges have remaining objects
        while ((j < mid2) && (k < max)) {
            if (anArray[j].compareTo(anArray[k]) < 0) {
                destArray[l++] = anArray[j++];
            }
            else {
                destArray[l++] = anArray[k++];
            }
        }

        // case where first and third ranges have remaining objects
        while ((i < mid1) && (k < max)) {
            if (anArray[i].compareTo(anArray[k]) < 0) {
                destArray[l++] = anArray[i++];
            }
            else {
                destArray[l++] = anArray[k++];
            }
        }

        // copy remaining objects from the first range
        while (i < mid1) {
            destArray[l++] = anArray[i++];
        }
        
        // copy remaining objects from the second range
        while (j < mid2) {
            destArray[l++] = anArray[j++];
        }

        // copy remaining objects from the third range
        while (k < max) {
            destArray[l++] = anArray[k++];
        }
    }
}