/**
* Abstract Comparison-based Sorting Algorithm, based on Susan Merritt's taxonomy :
* "An Inverted Taxonomy of Sorting Algorithms," Communication of the ACM, Jan. 1985,
* Volume 28, Number 1, pp. 96-99.  The template method pattern is used to implement
* this taxonomy.
* @author Dung X. Nguyen - Copyright 1999 - All rights reserved.
* @since 11/28/99
*/
public abstract class ASorter
{
	/**
    * 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(int[] 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(int[] 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(int[] A, int lo, int s, int hi);
}