Algorithms · topic
The divide, conquer and combine pattern and its recurrences: binary search, merge sort, quicksort, maximum and minimum in 3n/2 - 2 comparisons, fast exponentiation, Karatsuba and Strassen counts, inversion counting, maximum subarray and closest pair.
Merge sort is the standard example of divide and conquer. It splits the array into two halves, sorts each half recursively, and merges the two sorted halves in linear time. Its worst-case running time is Θ(n lg n), which matches the lower bound for comparison sorting, and it is stable.
Quicksort sorts by divide and conquer, but puts the work in the divide step. It chooses a pivot, partitions the array so that smaller elements come before larger ones, and then sorts the two parts recursively; no combine step is needed.
Divide and conquer solves a problem by splitting it into smaller instances of the same problem, solving those recursively, and combining their answers. Merge sort, quicksort and binary search are the familiar examples.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
