3.3. Divide & Conquer Sort

Merge sort, quick sort, intro sort

Divide & Conquer

• Divide the problem into sub-problems (recursively).

• Conquer sub-problems, which effectively solve the super problem.

Complexity	MergeSort	TimSort	QuickSort	IntroSort
Best	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$
Worst	$O(n \log n)$	$O(n\log n)$	$O(n^2)$	$O(n \log n)$
Average	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$

Why do people ever want to use QuickSort?

Merge Sort

• Divide the input array into two sub-arrays.

• Sort each of the sub-arrays and merge them into the back.

Let us create the MergeSort class inheriting AbstractSort:

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);
    }
}

• L2: holds the copy of the input array.

Let us then override the sort() method that calls the helper method:

@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);
}

• L4-5: increases the size of the temp array if necessary.

  • L5: unchecked type Object to T[].

What is the advantage of declaring the member field temp?

The helper method can be defined as follows:

/**
 * @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);
}

• L11: sorts the left sub-array.

• L12: sorts the right sub-array.

• L13: merges the left and right sub-arrays.

Finally, the merge() method can be defined as follows:

/**
 * @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++]);
    }
}

• L10-11: copies the input array to the temporary array and counts the assignments.

• L14-15: no key left in the 1st half.

• L16-17: no key left in the 2nd half.

• L18-19: the 2nd key is greater than the 1st key.

• L20-21: the 1st key is greater than or equal to the 2nd key.

How many assignments are made for the $n$ number of keys by the above version of MergeSort?

Quick Sort

• Pick a pivot key in the input array.

• Exchange keys between the left and right partitions such that all keys in the left and right partitions are smaller or bigger than the pivot key, respectively.

• Repeat this procedure in each partition, recursively.

Let us create the QuickSort class inheriting AbstractSort:

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

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

Let us then override the sort() method:

@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);
}

• L3: stops when the pointers are crossed.

• L6: sorts the left partition.

• L7: sorts the right partition.

The partition() method can be defined as follows:

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;
}

• L5: finds the left pointer where endIndex > fst > pivot.

• L6: finds the right pointer where beginIndex < snd < pivot.

• L7: the left and right pointers are crossed.

• L8: swaps between keys in the left and right partitions.

• L11: swaps the keys in the beginIndex and pivot.

The programming design in L5 and L6 are not ideal since the while loops do not include anybody that can confuse other programmers.

Intro Sort

• Although Quick Sort is the fastest on average, the worst-case complexity is $O(n^2)$.

• $\exists$ sorting algorithms that guarantee faster worst-case complexities than Quick Sort: $\Rightarrow$ Quick Sort for random cases and a different algorithm for the worst case.

How can we determine if Quick Sort is meeting the worse-case?

Let us define the IntroSoft class inheriting QuickSort:

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();
    }

}

• L2: declares a sorting algorithm to handle the worst cases.

• L14: resets the counters for both the main and auxiliary sorting algorithms.

We then override the sort() method by passing the maximum depth to the auxiliary method:

@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);
}

• L9: returns $2 \log n$ as the maximum depth.

Finally, the auxiliary method sort() can be defined as follows:

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);
    }
}

• L4-5: switches to the other sorting algorithm if the depth of the partitioning exceeds the max depth.

Does the max-depth need to be set to $2 \log n$?

Benchmarks

The following shows runtime speeds, assignment costs, and comparison costs between several sorting algorithms for the random, best, and worst cases.

https://www.slideshare.net/jchoi7s/dsajava-divide-conquer-sorting-algorithms-benchmarks