package Sorter;

/**
 * A concrete sorter that uses the Merge Sort method.
 */
public class MergeSorter extends ASorter
{
	/**
	 * Temporary array for merging.
	 */
	private Object[] _tempA = new Object[1];

	/**
	 * @param iCompareOp
	 */
	public MergeSorter(AOrder iCompareOp)
	{
		super(iCompareOp);
	}

	/**
	 * 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(Object[] A, int lo, int s, int hi)
	{
      int i = lo;
      int j = s;
      for (int k = lo; k <= hi; k++)
      {
         if ((i < s) && (j <= hi))
         {
            if (aOrder.lt(A[i], A [j]))
            {
               _tempA[k] = A[i++];
            }
            else
            {
               _tempA[k] = A[j++];
            }
         }
         else if (i < s)
         {
            _tempA[k] = A[i++];
         }
         else if (j <= hi)
         {
            _tempA[k] = A[j++];
         }
      }
	}

	/**
	 * Splits A[lo:hi] into A[lo:s-1] and A[s:hi] where s is the returned value of this function.
	 * Splits the sub-array in two.
	 * @param A the array A[lo:hi] to be sorted.
	 * @param lo the low index of A.
	 * @param hi the high index of A.
	 * @return (hi-lo)/2 always.
	 */
	public int split(Object[] A, int lo, int hi)
	{
		return ((lo + hi + 1)/2);
	}

	/**
	 * Joins sorted A[lo:s-1] and sorted A[s:hi] into A[lo:hi].
	 * This method uses the temporary array to merge the sub-arrays into and copies the data back to the original space.
	 * @param A A[lo:s-1] and A[s:hi] are sorted.
	 * @param lo the low index of A.
	 * @param s 
	 * @param hi the high index of A.
	 */
	public void join(Object[] A, int lo, int s, int hi)
	{
      _tempA = new Object [A.length];
      merge (A, lo, s, hi);
      for (int i = lo; i <= hi; i++)
      {
         A[i] = _tempA[i];
      }
	}
}