/**
* Splits the array in half, sorts each half, then merges the sorted halves together.
* The splitting is trivial.  The joining requires a temporary array to merge the
* sorted halves.  The tempory array then is copied back into the original array.
* @author Dung X. Nguyen - Copyright 1999 - All rights reserved.
* @since 11/28/99
*/
public class CMergeSorter extends ACompareSorter {
    /**
     * Temporary array for merging.
     */
    private IOrdered[] _tempA = new IOrdered[10];

    public CMergeSorter(int arraySize) {
        _tempA = new IOrdered[arraySize];
    }

    /**
    * Merges the sorted A[lx:mx-1] and the sorted A[mx:rx] into _tempA[lx:rx].
     * @param A  A[lx:mx-1] (left array) and A[mx:rx] (right array) are sorted.
     * @param lx the low index of the left array.
     * @param mx the low index of the right array, lx < mx <= rx.
     * @param rx the high index of the right array.
     */
    private void merge(IOrdered[] A, int lx, int mx, int rx) {
        int i = lx;
        int j = mx;
        for (int k = lx; k <= rx; k++) {
            if ((i < mx) && (j <= rx)) {
                if (A[i].compare (A [j]) == IOrdered.LESS) {
                   _tempA[k] = A[i++];
                }
                else {
                   _tempA[k] = A[j++];
                }
            }
            else if (i < mx) {
                _tempA[k] = A[i++];
            }
            else if (j <= rx) {
                _tempA[k] = A[j++];
            }
        }
    }

    /**
    * Splits the array in half.
     * @param A
     * @param lo the low index of A.
     * @param hi the high index of A.
     * @return s == (lo + hi + 1)/2
     */
    protected int split(IOrdered[] A, int lo, int hi) {
        return ((lo + hi + 1)/2);
    }

    /**
    * Merges A[lo:s-1] and A[s:hi] into _tempA[lo:hi], then copies _tempA back to A.
     * @param A  A[lo:s-1] and A[s:hi] are sorted.
     * @param lo the low index of A.
     * @param s  == (lo + hi + 1)/2
     * @param hi the high index of A.
     */
    protected void join(IOrdered[] A, int lo, int s, int hi) {
        merge (A, lo, s, hi);
        for (int i = lo; i <= hi; i++) {
            A[i] = _tempA[i];
        }
    }
}