/**
* 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 MergeSorter extends ASorter {
    /**
    * Temporary array for merging.
    */
    private int[] _tempA;

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

    /**
    * 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
    */
    public int split(int[] 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.
    */
    public void join(int[] A, int lo, int s, int hi) {
        merge (A, lo, s, hi);
        for (int i = lo; i <= hi; i++) {
            A[i] = _tempA[i];
        }
    }

    /**
    * 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 final void merge(int[] 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] < A [j]) {
                    _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++];
            }
        }
    }

    /**
    * Tests MergeSorter.
    */
    public static void main(String[] args) {
        int[] A =  {99, -34, 0, 5, -7, 0};
        int arrayLen = A.length;
        System.out.println ("A =");
        for (int i = 0; i < arrayLen; i++) {
            System.out.print (A[i] + "  ");
        }
        System.out.println ();
        System.out.println ("Sorting A...");
        new MergeSorter (arrayLen).sort (A, 0, arrayLen - 1);
        System.out.println ("Sorted A =");
        for (int i = 0; i < A.length; i++) {
            System.out.print (A[i] + "  ");
        }
        System.out.println ("\nDone");
    }
}