//package Sorter;

/**
 * An abstract sorter of IOrdered objects.
 * IOrdered is similar to java.lang.Comparable.
 * @author D. X. Nguyen
 * @author S. B. Wong
 */
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] of IOrdered objects 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.
     */
    protected 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.
     */
    protected abstract void join(IOrdered[] A, int lo, int s, int hi);

    /**
    * Initializes this ACompareSorter to a proper state before sorting.
    * The default behavior is do nothing.  Concrete subclasses should override if necessary.
    */
    protected void init ()  {
    // Default: does nothing.
    }
}