Classical D&C Algorithms

Four algorithms cover most of what gets taught under “divide and conquer.” All four are direct applications of the template — once you see them through the D&C lens, the structure is identical.

1. Merge Sort

Sort an array.

Divide: cut the array in half.
Conquer: recursively sort each half.
Combine: merge the two sorted halves.

The merge step is the heart of the algorithm. Two-pointer pass over both halves, picking the smaller front element each time.

Recurrence: T(n) = 2 T(n/2) + O(n) → O(n log n). Space: O(n) for the temp buffer, O(log n) for the recursion stack. Stable: yes (use <= not < in the merge tie-break).

Why merge sort is worth knowing even when sort libraries exist

It’s the foundation for inversion counting, count smaller after self, reverse pairs — all problems that piggyback extra accounting on the merge step.
It’s the canonical stable comparison sort.
It parallelizes naturally — the left and right halves are independent.
It’s used in external sorting (sorting data that doesn’t fit in memory).

2. Quicksort

Sort an array, in place.

Divide: pick a pivot, partition the array so elements < pivot come first, > pivot last.
Conquer: recursively sort the left and right partitions.
Combine: nothing — the partition step has already sorted across the pivot.

The combine is trivial (the partition does the work). The “real” cost is in the partition.

Recurrence (average): T(n) = 2 T(n/2) + O(n) → O(n log n). Recurrence (worst): T(n) = T(n - 1) + O(n) → O(n²) (e.g., already-sorted input with a bad pivot choice). Space: O(log n) recursion stack on average; O(n) worst case. Stable: no.

Pivot selection — the practical knob

Bad pivot choice ruins quicksort. Three common strategies:

Last element as pivot (Lomuto, shown above) — O(n²) on sorted input.
Random pivot — O(n log n) expected.
Median-of-three — middle of first/middle/last; cheap heuristic that empirically avoids most worst cases.

Library implementations (C++ std::sort, Java Arrays.sort) use introsort — quicksort that bails to heapsort if the recursion goes too deep, guaranteeing O(n log n) worst-case.

3. Binary Search

Find a target in a sorted array.

Divide: look at the middle element.
Conquer: if not the target, recurse on the half that could contain it.
Combine: nothing — just return the answer from the conquer step.

Recurrence: T(n) = T(n/2) + O(1) → O(log n). Space: O(log n) recursion (or O(1) if iterative).

The iterative version is almost always preferred

In production code, binary search is written iteratively to avoid recursion overhead. We covered the full iterative template — including the unified “find first true” approach — in Day 13. The recursive form is here to make the D&C shape explicit; the iterative form is what you’d ship.

4. Fast Exponentiation

Compute x^n for integer n.

Naïve: multiply x by itself n times. O(n). D&C: x^n = (x^(n/2))² · (x if n is odd else 1).

Divide: compute x^(n/2).
Conquer: recurse.
Combine: square and (optionally) multiply by x once more.

Recurrence: T(n) = T(n / 2) + O(1) → O(log n). Space: O(log n) recursion.

⚠️

Always promote n to a wider type before negating. INT_MIN is -2^31; -INT_MIN overflows int. Use long long in C++/Java, or rely on Python’s unbounded ints. This is a very-common, easy-to-miss bug.

The iterative bit-shift version

For modular arithmetic (x^n mod p with n up to 10^18), the iterative bit-shift form is more common:

def pow_mod(x, n, mod):
    result = 1
    x %= mod
    while n > 0:
        if n & 1: result = (result * x) % mod
        x = (x * x) % mod
        n >>= 1
    return result

Same O(log n) time, O(1) space.

A side-by-side summary

Algorithm	Recurrence	Time	Space	Stable	Notes
Merge sort	`T(n) = 2T(n/2) + O(n)`	`O(n log n)`	`O(n)`	Yes	Foundation for inversion counting
Quicksort	`T(n) = 2T(n/2) + O(n)` avg	`O(n log n)` avg, `O(n²)` worst	`O(log n)` avg	No	In place; pivot choice matters
Binary search	`T(n) = T(n/2) + O(1)`	`O(log n)`	`O(log n)` recursive, `O(1)` iterative	—	Requires sorted input
Fast exponentiation	`T(n) = T(n/2) + O(1)`	`O(log n)`	`O(log n)` recursive, `O(1)` iterative	—	Watch for INT_MIN overflow

All four are instances of the same template. The variation comes entirely from how many recursive calls and how expensive the combine step is.

Quick check

In merge sort, why is the merge step's stability (using <= instead of <) important?

Quicksort's worst case is O(n²). Why isn't it disqualified from real-world use?

Fast exponentiation: computing x^n by halving n. Why is the recursion depth O(log n), not O(n)?

Next: advanced patterns — Karatsuba multiplication, Strassen’s matrix multiply, closest pair of points, and the FFT preview.

The Master Theorem Advanced Patterns