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

   /**
   * 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");
	}

	/**
    * Merges A[lx:lxHi] and A[rxLo:rx] into _tempA[tempLo:tempLo + (lxHi-lx+1) + (rx-rxLo+1)].
    * Calls mergeHelp for the case lx <= lxHi (i.e. left array is not empty).
	 * @param A  A[lx:lxHi] (left array) and A[rxLo:rx] (right array) are sorted.
	 * @param lx the low index of the left array.
	 * @param lxHi the high index of the left array.
	 * @param rxLo the low index of the right array.
	 * @param rx   the high index of the right array.
	 * @param tempLo the lo index of _tempA into which the left and right arrays are merged.
	 */
	private void merge(int[] A, int lx, int lxHi, int rxLo, int rx, int tempLo)
	{
      if (lx <= lxHi)
      {
         mergeHelp (A, lx, lxHi, rxLo, rx, tempLo);
      }
      else
      {
         // Copy right array A[rxLo:rx] into _tempA:
         for (int i = rxLo; i <= rx; i++)
         {
            _tempA[tempLo++] = A[i];
         }
      }
	}

	/**
    * Merges A[lx:lxHi] and A[rxLo:rx] into _tempA[tempLo:tempLo + (lxHi-lx+1) + (rx-rxLo+1)],
    * knowing lx <= lxHi (i.e. left array is not empty).
	 * @param A  A[lx:lxHi] (leeft array) and A[rxLo:rx] (right array) are sorted.
	 * @param lx the low index of the left array, <= lxHi.
	 * @param lxHi the high index of the left array, >= lx.
	 * @param rxLo the low index of the right array.
	 * @param rx   the high index of the right array.
	 * @param tempLo the lo index of _tempA into which the left and right arrays are merged.
	 */
	private void mergeHelp(int[] A, int lx, int lxHi, int rxLo, int rx, int tempLo)
	{
      if (rx < rxLo)  // right array A[rxLo:rx] is empty.
      {
         // Copy left array A[lx:lxHi] into _tempA:
         for (int i = lx; i <= lxHi; i++)
         {
            _tempA[tempLo++] = A[i];
         }
      }
      else if (A[lx] < A[rxLo])
      {
         _tempA[tempLo++] = A[lx];
         mergeHelp (A, rxLo, rx, lx + 1, lxHi, tempLo);
      }
      else
      {
         _tempA[tempLo++] = A[rxLo];
         mergeHelp (A, lx, lxHi, rxLo + 1, rx, tempLo);
      }
	}
}