Divide and conquer

Here is one of the most productive ideas in all of computing, and it fits in three words: divide, conquer, combine. Cut the input into smaller independent parts, solve each part by the very same method (that is the recursion), then merge the partial answers into the whole. The pattern is easy. The interesting question is always the bill - and the bill is written as a recurrence like $T(n)=2T(n/2)+O(n)$, which the Master Theorem reads off almost by eye.

Counting the cost: recurrences and the Master Theorem

A recursive algorithm's running time is defined in terms of itself on smaller inputs. If a problem of size $n$ makes $a$ recursive calls on inputs of size $n/b$, plus $f(n)$ non-recursive work to split and combine, then its total time obeys

Merge sort makes $a=2$ calls on halves ($b=2$) and merges in linear time, so $T(n)=2T(n/2)+O(n)$. To turn that self-referential equation into a plain Big-O, picture the recursion tree: level $i$ has $a^i$ nodes, each of size $n/b^i$, so the work on that level is $a^{i}f(n/b^i)$. The total is the sum down all ${\log }_{b}n$ levels - and everything hinges on a single race between two numbers: $a$ (how fast the tree widens) versus $b^d$ (how fast the work shrinks, when $f(n)=\Theta (n^d)$).

See it work

Two coupled toys in one. Top: watch merge sort build its recursion tree - step down as the 8-element array divides into halves until every leaf is a single element, then step back up as each pair of sorted runs merges (the amber pair is the two fronts being compared; the smaller one drops into the parent). Bottom: tune $a$, $b$, and the exponent $d$ of $f(n)=\Theta (n^d)$ and read off which Master Theorem case you land in - the presets drop you onto the real algorithms above.

The same shape, everywhere

Binary search is divide and conquer with a trivial combine: it throws away a whole half after one comparison and never has to glue anything back, so $T(n)=T(n/2)+O(1)=O(\log n)$ (Case 2 with $d=0$). Karatsuba multiplies two $n$-digit numbers with only $a=3$ half-size multiplications instead of the schoolbook 4 - dropping one subproblem changes ${\log }_{2}4=2$ into ${\log }_{2}3\approx 1.585$, so $\Theta (n^2)$ becomes $\Theta (n^{1.585})$. And the maximum-subarray problem splits the array in two, recurses on each half, and combines by finding the best sub-array that crosses the midpoint in $O(n)$ - the same $2T(n/2)+O(n)=\Theta (n\log n)$ as merge sort. Here is the canonical combine, the merge:

def merge_sort(a):
    if len(a) <= 1:                 # base case: 0 or 1 items are already sorted
        return a
    mid   = len(a) // 2              # DIVIDE at the midpoint
    left  = merge_sort(a[:mid])       # CONQUER - recurse on each half
    right = merge_sort(a[mid:])
    return merge(left, right)       # COMBINE the two sorted halves

def merge(left, right):              # zip two sorted runs into one, in O(n)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # take the smaller of the two fronts
            out.append(left[i]);  i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one side is empty - drain the other
    out.extend(right[j:])
    return out

Check yourself