3.3. Divide & Conquer Sort

public class MergeSort<T extends Comparable<T>> extends AbstractSort<T> {
    private T[] temp;

    public MergeSort() {
        this(Comparator.naturalOrder());
    }

    public MergeSort(Comparator<T> comparator) {
        super(comparator);
    }
}

@Override
@SuppressWarnings("unchecked")
public void sort(T[] array, int beginIndex, int endIndex) {
    if (temp == null || temp.length < array.length)
        temp = (T[])Array.newInstance(array[0].getClass(), array.length);
    sort(array, temp, beginIndex, endIndex);
}

/**
 * @param input the input array.
 * @param temp the array to hold the copy of the input array.
 * @param beginIndex the beginning index of the 1st half (inclusive).
 * @param endIndex the ending index of the 2nd half (exclusive).
 */
protected void sort(T[] input, T[] copy, int beginIndex, int endIndex) {
    if (beginIndex + 1 >= endIndex) return;
    int middleIndex = Utils.getMiddleIndex(beginIndex, endIndex);

    sort(input, copy, beginIndex, middleIndex);
    sort(input, copy, middleIndex, endIndex);
    merge(input, copy, beginIndex, middleIndex, endIndex);
}

/**
 * @param input the input array.
 * @param temp the array to hold the copy of the input array.
 * @param beginIndex  the beginning index of the 1st half (inclusive).
 * @param middleIndex the ending index of the 1st half (exclusive).
 * @param endIndex    the ending index of the 2nd half (exclusive).
 */
protected void merge(T[] input, T[] copy, int beginIndex, int middleIndex, int endIndex) {
    int fst = beginIndex, snd = middleIndex, n = endIndex - beginIndex;
    System.arraycopy(input, beginIndex, copy, beginIndex, n);
    assignments += n;

    for (int k = beginIndex; k < endIndex; k++) {
        if (fst >= middleIndex)
            assign(input, k, copy[snd++]);
        else if (snd >= endIndex)
            assign(input, k, copy[fst++]);
        else if (compareTo(copy, fst, snd) < 0)
            assign(input, k, copy[fst++]);
        else
            assign(input, k, copy[snd++]);
    }
}

public class QuickSort<T extends Comparable<T>> extends AbstractSort<T> {
    public QuickSort() {
        this(Comparator.naturalOrder());
    }

    public QuickSort(Comparator<T> comparator) {
        super(comparator);
    }
}

@Override
public void sort(T[] array, int beginIndex, int endIndex) {
    if (beginIndex >= endIndex) return;

    int pivotIndex = partition(array, beginIndex, endIndex);
    sort(array, beginIndex, pivotIndex);
    sort(array, pivotIndex + 1, endIndex);
}

protected int partition(T[] array, int beginIndex, int endIndex) {
    int fst = beginIndex, snd = endIndex;

    while (true) {
        while (++fst < endIndex && compareTo(array, beginIndex, fst) >= 0);
        while (--snd > beginIndex && compareTo(array, beginIndex, snd) <= 0);
        if (fst >= snd) break;
        swap(array, fst, snd);
    }

    swap(array, beginIndex, snd);
    return snd;
}

public class IntroSort<T extends Comparable<T>> extends QuickSort<T> {
    private final AbstractSort<T> engine;

    public IntroSort(AbstractSort<T> engine) {
        this(engine, Comparator.naturalOrder());
    }

    public IntroSort(AbstractSort<T> engine, Comparator<T> comparator) {
        super(comparator);
        this.engine = engine;
    }

    @Override
    public void resetCounts() {
        super.resetCounts();
        if (engine != null) engine.resetCounts();
    }

}

@Override
public void sort(T[] array, int beginIndex, int endIndex) {
    final int maxdepth = getMaxDepth(beginIndex, endIndex);
    sort(array, beginIndex, endIndex, maxdepth);
    comparisons += engine.getComparisonCount();
    assignments += engine.getAssignmentCount();
}

protected int getMaxDepth(int beginIndex, int endIndex) {
    return 2 * (int)Utils.log2(endIndex - beginIndex);
}

private void sort(T[] array, int beginIndex, int endIndex, int maxdepth) {
    if (beginIndex >= endIndex) return;

    if (maxdepth == 0)    // encounter the worst case
        engine.sort(array, beginIndex, endIndex);
    else {
        int pivotIndex = partition(array, beginIndex, endIndex);
        sort(array, beginIndex, pivotIndex, maxdepth - 1);
        sort(array, pivotIndex + 1, endIndex, maxdepth - 1);
    }
}