//package Sorter;

public abstract class ACompareSorter
{
	/**
    * Sorts by doing a split-sort-sort-join.  Splits the original array into two subarrays,
    * recursively sorts the split subarrays, then re-joins the sorted subarrays together.
    * This is the template method.  It calls the abstract methods split and join to do
    * the work.  All comparison-based sorting algorithms are concrete subclasses with
    * specific split and join methods.
	 * @param A the array A[lo:hi] to be sorted.
	 * @param lo the low index of A.
	 * @param hi the high index of A.
	 */
	public final void sort(IOrdered[] A, int lo, int hi)
	{
      if (lo < hi)
      {
         int s = split (A, lo, hi);
         sort (A, lo, s-1);
         sort (A, s, hi);
         join (A, lo, s, hi);
      }
	}

	/**
    * Splits A[lo:hi] into A[lo:s-1] and A[s:hi] where s is the returned value of this function.
	 * @param A the array A[lo:hi] to be sorted.
	 * @param lo the low index of A.
	 * @param hi the high index of A.
	 */
	public abstract int split(IOrdered[] A, int lo, int hi);

	/**
    * Joins sorted A[lo:s-1] and sorted A[s:hi] into A[lo:hi].
	 * @param A A[lo:s-1] and A[s:hi] are sorted.
	 * @param lo the low index of A.
	 * @param hi the high index of A.
	 */
	public abstract void join(IOrdered[] A, int lo, int s, int hi);
}