Divide and conquer

Divide splits the input into smaller instances of the same problem. For an array, that usually means the two halves around mid; for a number, it means n / 2; for a list, the head and the rest.

The subproblems should be independent (they do not share work) and of the same kind as the original. If they overlap, you are in the territory of dynamic programming (Chapter 23).

Conquer solves each subproblem recursively. When a subproblem is small enough, solve it directly: that is the base case. Libraries often switch to a simple method (such as insertion sort) at a small size because recursion has overhead.

In the animation, max(lo, hi) calls itself on both halves. Each box in the tree is one conquered subproblem, with its answer once it returns.

1static int max(int[] a, int lo, int hi) {
2    if (lo == hi) return a[lo];                 // one element: it is the max
3    int mid = lo + (hi - lo) / 2;               // divide
4    int left = max(a, lo, mid);                 // conquer left half
5    int right = max(a, mid + 1, hi);            // conquer right half
6    return Math.max(left, right);               // combine
7}

Combine builds the answer to the whole problem from the answers to its parts. For the maximum it is one comparison; for merge sort it is an O(n) merge; for counting inversions it is a merge plus a count. For quick sort the combine step is empty, because all the work is in the divide (partition).

The cost of combining at each level is what the recurrence T(n) = a·T(n/b) + f(n) calls f(n). Cheap combines give linear algorithms; expensive ones may not help at all.

If each split is balanced (halves), the tree has about log₂ n levels. If the split is lopsided (sizes n - 1 and 1), it has n levels and the algorithm behaves like a linear chain.

Merge sort always splits in the middle, so it is always O(n log n). Quick sort splits at the pivot, so a bad pivot gives O(n²). That is the whole difference between a worst case that is guaranteed good and one that depends on the data.

Draw the tree of subproblems and add up the work per level. For merge sort: level 0 has 1 problem of size n, level 1 has 2 of size n / 2, level k has 2^k of size n / 2^k, so every level does n work in total over log₂ n levels.

The calculator in the next lesson computes these level totals for any a, b and d. Whether the top, the bottom or all levels dominate decides the answer.

Merge sort divides at the middle, conquers by sorting each half, and combines by merging two sorted halves in linear time. The recurrence is T(n) = 2·T(n/2) + O(n), which solves to O(n log n).

Its easy combine step is the key: merging two sorted lists is a single pass. Step through the animation and notice that all the sorting happens inside the merges, on the way back up.

1public static void mergeSort(int[] arr, int lo, int hi) {
2    if (hi - lo < 1) return;
3    int mid = lo + (hi - lo) / 2;
4    mergeSort(arr, lo, mid);
5    mergeSort(arr, mid + 1, hi);
6    merge(arr, lo, mid, hi);
7}
8
9static void merge(int[] arr, int lo, int mid, int hi) {
10    int[] tmp = new int[hi - lo + 1];
11    int i = lo, j = mid + 1, k = 0;
12    while (i <= mid && j <= hi) {
13        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
14        else tmp[k++] = arr[j++];
15    }
16    while (i <= mid) tmp[k++] = arr[i++];
17    while (j <= hi) tmp[k++] = arr[j++];
18    System.arraycopy(tmp, 0, arr, lo, tmp.length);
19}

Quick sort puts the work in the divide: partition around a pivot so that everything smaller is on the left and everything larger on the right. The conquer step sorts both sides, and the combine step is empty, because the pieces are already in the right order.

Its running time depends entirely on how balanced the partitions are. Change the Pivot option and run the sorted-input preset to watch the tree become a chain.

1public static void quickSort(int[] arr, int lo, int hi) {
2    if (lo >= hi) return;
3    int p = partition(arr, lo, hi);
4    quickSort(arr, lo, p - 1);
5    quickSort(arr, p + 1, hi);
6}
7
8static int partition(int[] arr, int lo, int hi) {
9    movePivotToEnd(arr, lo, hi);          // strategy: last, first, middle, median of 3
10    int pivot = arr[hi];
11    int i = lo;                            // arr[lo..i-1] < pivot
12    for (int j = lo; j < hi; j++) {
13        if (arr[j] < pivot) {
14            swap(arr, i, j);
15            i++;
16        }
17    }
18    swap(arr, i, hi);                      // pivot to its final place
19    return i;
20}