/**
 * A merge sort implementation
 * Actually several different merge sort implementations.
 * The basic implementation uses the functions domergesort and domerge
 * This implementation is woefully slow because it allocates new arrays 
 * for every merge then has to do a final copy for make the sort change the
 * original list.
 * 
 * Much faster is mergesort3 and its companion domergesort3 and mergeparts3
 * which use a secondary array of the size of the array to be sorted as
 * a merge site, therefore avoiding a lot of array allocations (this extra
 * array is clevery named tempmergearray.)
 * 
 * finally, slightly faster still is mergesort3i with uses insertion sort
 * when the splits get small (say 16-ish) so avoid meny recursive calls.
 * This gives a small speed bump. 
 *  
 * @author gtowell
 * created: April 15, 2020
 */
public class Merge extends SortBase {
    
    /**
     * Merge the two lists
     * @param list1 the first list, sorted
     * @param list2 the second list, sorted
     * @return a new list (array) containing all of the eleents of lsist1 and list2, sorted.
     */
    private int[] domerge(int[] list1, int[] list2)
    {
        int[] rtn = new int[list1.length + list2.length];
        int locr=0, loc1=0, loc2=0;
        while (loc1<list1.length && loc2<list2.length) 
        {
            if (list1[loc1] > list2[loc2])
            {
                rtn[locr++]=list2[loc2++];
            }
            else
            rtn[locr++]=list1[loc1++];
        }
        for (int i=loc1; i<list1.length; i++)
        rtn[locr++]=list1[i];
        for (int i=loc2; i<list2.length; i++)
        rtn[locr++]=list2[i];
        return rtn;
    }
    
    @Override
    public void sortInPlace(int[] list) {
        int[] aa = doMergeSort(list, 0, list.length-1);
        // change the contents of the provided array
        for (int i=0; i<list.length; i++)
            list[i]=aa[i];
    }
    
    /**
     * The internal, recursive implementation of merge sort
     */
    private int[] doMergeSort(int[] list, int strt, int eend) {
        if (eend==strt)
        {
            int[] tmp = new int[1];
            tmp[0]=list[strt];
            return tmp;
        }
        if (eend<strt)
            return new int[0];
        int mid = (strt+eend)/2;
        return domerge(doMergeSort(list, strt, mid), doMergeSort(list, mid+1, eend));
    }
    

    
    
    /** A temp array used by a faster merge sort */
    private int[] array;
    /** Another temp array */
    private int[] tempMergArr;
    /**
     * A faster version of mergesort, using two arrays rather than allocating new 
     * constantly.
     * Note that this versio should ne be used in multi-threaded systems
     * @param inputArr the array to be sorted
     * @return the sorted array
     */
    public int[] mergesort3(int inputArr[]) {
        this.array = inputArr;
        this.tempMergArr = new int[inputArr.length];
        doMergeSort3(0, inputArr.length - 1);
        return array;
    }
    
    /**
     * The actual implementation of the faster merge sort.
     * @param lowerIndex the smallest index of the part of the array to be sorted
     * @param higherIndex the largest index
     */
    private void doMergeSort3(int lowerIndex, int higherIndex) {

        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
            doMergeSort3(lowerIndex, middle);
            // Below step sorts the right side of the array
            doMergeSort3(middle + 1, higherIndex);
            // Now merge both sides
            mergeParts3(lowerIndex, middle, higherIndex);
        }
    }
    


    /** An instance of Insertion sort used by mergesort3i, this is a lousy thing
     * do do, but since the point of 3i is speed doing lousy things is OK
    */
    private Insertion iSort;

    /**
     * A yet faster version of mergesort.  This verion uses the inplace trick of v3
     * then adds another trick -- calling insertion sort when the size of the splits
     * gets small. Doing so avoids a ton of recursive calls, thereby speeding things up
     * (Lesson, at small sizes, insertion sort is faster than merge sort.) 
     * @param inputArr the array to be sorted
     * @return the sorted array
     */
    public int[] mergesort3i(int inputArr[]) {
        iSort = new Insertion();
        this.array = inputArr;
        this.tempMergArr = new int[inputArr.length];
        doMergeSort3i(0, inputArr.length-1);
        return array;
    }

    /**
     * A private recursive function to actually do the work for v3i
     * @param lowerIndex the lowest index in the array to be sorted
     * @param higherIndex the highest index in the array to be sorted
     */
    private void doMergeSort3i(int lowerIndex, int higherIndex) {
        
        if (lowerIndex > (higherIndex-12)) {
            iSort.insertionSortIP(array, lowerIndex, higherIndex);
        } else if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
            doMergeSort3i(lowerIndex, middle);
            // Below step sorts the right side of the array
            doMergeSort3i(middle + 1, higherIndex);
            // Now merge both sides
            mergeParts3(lowerIndex, middle, higherIndex);
        }
    }

    
    /**
     * Merge using the temp array.  Note that the items in  lowerIndex--midddle are sorted
     * as are the items middle--higherIndex
     * @param lowerIndex the lower index
     * @param middle the middle
     * @param higherIndex the top index
     */
    private void mergeParts3(int lowerIndex, int middle, int higherIndex) {
        // copy into temp
        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        // copy back from temp to main array
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }
        // do not need to copy upper half is that remains because the upper is already there
    }
    
}