Divide & Conquer
You have a pile of 1,000 exam papers to sort by name. You could take them one at a time and slot each into the right place in a growing sorted pile: about half a million comparisons. Or you could split the pile in two, give each half to a friend, ask each friend to do the same with their half, and so on, until each person holds one paper — then merge the sorted piles back together on the way up. The second plan needs about 10,000 comparisons. That is divide and conquer: break the problem into smaller problems of the same kind, solve those recursively, and combine their answers.
You met this idea in Merge Sort, Quick Sort and Binary Search. This lesson turns it from "a trick some sorting algorithms use" into a design method you can apply to geometry, arithmetic and arrays. You will count inversions, find the closest pair among a million points in , multiply two -digit numbers with fewer than digit products, see how Strassen beat for matrices and why your linear-algebra library ignores him, and learn to read the running time of any of these straight off its recurrence.
This lesson assumes Recursion & Induction and the recurrences section of Complexity Analysis. It is lesson 2 of Module 5 · Algorithmic Paradigms.
Why it exists
Many problems have an obvious quadratic algorithm: compare every pair. Inversions: check every pair . Closest points: measure every pair. Multiplication: multiply every digit of one number by every digit of the other. For , "every pair" is operations — minutes to hours. Divide and conquer is the most common way to get from to or , and it does it by making the pair-checking happen only across a split, where structure (sortedness, geometry, algebra) makes it cheap.
The history is a list of surprises:
- 1945: John von Neumann describes merge sort for the EDVAC — the first divide-and-conquer algorithm written for a stored-program computer (Knuth, TAOCP Vol. 3, §5.2.4).
- 1960: Andrey Kolmogorov conjectures in a Moscow seminar that multiplying two -digit numbers needs on the order of digit operations. Within a week, 23-year-old student Anatoly Karatsuba finds an algorithm, refuting it (published 1962, with Ofman).
- 1965: Cooley and Tukey publish the fast Fourier transform, instead of — a divide-and-conquer algorithm that is now in every phone, modem and audio codec.
- 1969: Volker Strassen shows that two matrices can be multiplied in , not , in a paper titled "Gaussian elimination is not optimal".
- 1975: Shamos and Hoey give the closest-pair algorithm, founding computational geometry as a field.
The common thread: the obvious algorithm does redundant work, and splitting the input exposes the redundancy.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "count pairs with some order property" (inversions, , range sums in ) | Merge-sort counting: count the cross pairs while merging |
| "closest pair", "minimum distance" among points | Closest-pair divide and conquer, or a grid/hash for expected |
| Multiply huge integers or polynomials | Karatsuba, then Toom–Cook or FFT for bigger sizes |
| Raise to a huge power, , -th Fibonacci, matrix power | Fast exponentiation (repeated squaring) |
| "-th smallest", "median", "top " without full sorting | Quickselect: recurse into one side only |
| "maximum subarray / sum", and the split point matters | Divide and conquer with a crossing case, or Kadane |
| An expression or structure that can be split at every operator or root | Split at each position, combine both sides' results (often with memoization) |
| Merge sorted lists | Pair them up and merge recursively: |
| Input splits into two halves whose answers combine in or less | , which is |
| Sorted array or monotone predicate, "find the boundary" | Binary search — divide and conquer that throws one half away |
| "Build a balanced tree / index from a sorted list" | Pick the middle as the root, recurse on both halves |
| Subproblems repeat (the same range or prefix is asked many times) | Not plain divide and conquer: add memoization, i.e. dynamic programming |
The meta-trigger: the brute force looks at all pairs, and you can say something cheap about the pairs that straddle a midpoint.
Intuition & first principles
The three steps
Every divide-and-conquer algorithm has the same shape:
- Divide the input into smaller pieces, each of size about . Usually : two halves.
- Conquer each piece by calling the same algorithm recursively. Pieces that are small enough (one element, two points, one digit) are solved directly — the base case.
- Combine the pieces' answers into the answer for the whole input.
All the cleverness is in step 3. Splitting an array in half is trivial; knowing what to do with two half-answers is the algorithm.
A tiny example: who is the tallest?
Find the tallest of 8 people. Split them into two groups of 4, find the tallest in each group (recursively: split each into two groups of 2, and so on), then compare the two winners. The combine step is a single comparison.
graph TD
A["8 people: tallest?"] --> B["left 4"]
A --> C["right 4"]
B --> D["2"]
B --> E["2"]
C --> F["2"]
C --> G["2"]
D --> H["compare 1 vs 1"]
E --> I["compare 1 vs 1"]
F --> J["compare 1 vs 1"]
G --> K["compare 1 vs 1"]
Count comparisons: 4 at the bottom level, 2 above, 1 at the top — 7 in total, exactly as many as a plain left-to-right scan. Divide and conquer did not help here, and it is worth seeing why: the combine step is and the plain scan is already , the best possible. Divide and conquer pays off when the brute force does more work than the recursion tree needs. For "tallest", brute force is linear; for "closest pair", brute force is quadratic, and that is where the method shines.
Why splitting can save work: the pairs argument
Take counting inversions: pairs with . Brute force checks all pairs. Split the array into a left half and a right half . Every pair is of exactly one of three kinds:
- both in — counted by the recursive call on ;
- both in — counted by the recursive call on ;
- one in , one in — the cross pairs.
There are cross pairs, a quarter of all pairs, so checking them one by one would gain nothing. The trick is that if both halves come back sorted, the cross pairs can be counted in one linear merge pass without looking at them individually (the Mechanics section shows how). Linear combine, two half-size calls: .
That is the pattern for most of this lesson. The recursion handles the pairs inside each half. The combine step handles the pairs across the split — and it must do that in much less than one step per cross pair.
Divide and conquer vs its relatives
| Paradigm | Subproblems | Example |
|---|---|---|
| Divide and conquer | several, independent (disjoint inputs), all solved | merge sort, Karatsuba, closest pair |
| Decrease and conquer | one smaller subproblem | binary search, fast exponentiation, quickselect |
| Dynamic programming | many, overlapping (the same subproblem reached many ways) | Fibonacci, edit distance |
| Backtracking | one per choice, explored until one fails | N-Queens, Sudoku |
"Independent" is the important word. Merge sort's two halves share no elements, so solving one tells you nothing about the other and nothing is computed twice. When a recursion reaches the same subproblem along different paths — fib(n-1) and fib(n-2) both call fib(n-3) — plain divide and conquer is exponential, and you need dynamic programming instead.
The template
# fragment — the shape of every divide-and-conquer algorithm
def solve(problem):
if is_small(problem): # base case: solve directly
return solve_directly(problem)
parts = divide(problem) # a pieces of size about n / b
answers = [solve(p) for p in parts] # conquer: independent recursive calls
return combine(answers, problem) # the real algorithm lives here
Four design questions, to answer on paper before you code:
- How do I split? By position (halves of an array), by value (quicksort's pivot), by geometry (a vertical line through the median point), by digits (high and low halves of a number).
- What must a recursive call return? Often more than the final answer. Inversion counting returns the count and the sorted half. Closest pair returns the distance and the points sorted by . Maximum subarray, in its form, returns four numbers. Strengthening what the recursion returns is the most common move in divide-and-conquer design — it is the same move as strengthening an induction hypothesis.
- How do I combine, and what does it cost? This decides the running time.
- What is the base case? Small enough that brute force is correct and cheap. In practice, a base case of 16–64 elements (switching to insertion sort or the schoolbook method) is faster than recursing down to 1.
Recurrences and the Master theorem (recap)
The running time of a divide-and-conquer algorithm is a recurrence: an equation that defines in terms of on smaller inputs. If the algorithm makes recursive calls on inputs of size and spends dividing and combining:
Complexity Analysis solves these three ways (substitution, recursion trees, the Master theorem). Here is the recursion-tree view, which explains the theorem instead of memorising it.
At depth of the recursion tree there are subproblems, each of size , so the work at that level is . The tree has levels, and the bottom level has leaves. The critical exponent is . Compare with :
| Case | Condition | Which levels dominate | |
|---|---|---|---|
| 1 | for some | the leaves: work grows geometrically downward | |
| 2 | , | every level does about the same work | |
| 3 | and for some | the root: work shrinks geometrically downward |
Every algorithm in this lesson, read off the table:
| Algorithm | Recurrence | , , | Case | Result |
|---|---|---|---|---|
| Binary search | 1, 2, 0 | 2 () | ||
| Fast exponentiation (in the exponent ) | 1, 2, 0 | 2 | multiplications | |
| Merge sort, inversion counting | 2, 2, 1 | 2 () | ||
| Closest pair (merge by ) | 2, 2, 1 | 2 | ||
| Closest pair (re-sort the strip each time) | 2, 2, 1 | 2 () | ||
| Maximum subarray, simple D&C | 2, 2, 1 | 2 | ||
| Maximum subarray, four-value D&C | 2, 2, 1 | 1 | ||
| Schoolbook multiplication, split in 4 | 4, 2, 2 | 1 | — no gain | |
| Karatsuba | 3, 2, 1.585 | 1 | ||
| Block matrix multiplication | 8, 2, 3 | 1 | — no gain | |
| Strassen | 7, 2, 2.807 | 1 | ||
| Quickselect, expected | on average | 1, 2, 0 | 3 | expected |
Two rows are worth staring at. Splitting multiplication into four half-size products gives again — splitting by itself saves nothing. Karatsuba's whole contribution is changing from 4 to 3, and since case 1 means "the leaves dominate", the number of leaves, , is the running time. Strassen is the same story with 8 → 7. When the leaves dominate, reduce the number of recursive calls; when the root dominates, speed up the combine step; when every level costs the same, you pay a factor and both matter.
Deeper: when the Master theorem does not apply
It needs equal-sized subproblems and a polynomial-ish gap between and . Recurrences like (uneven splits) need a recursion tree or the Akra–Bazzi method; the answer here is , because every level sums to at most and there are levels. Median of medians has ; since , the levels shrink geometrically and . Quicksort's worst case, , is not of the form at all; it sums to . See Complexity Analysis.
Mechanics
1. Counting inversions with merge sort
An inversion is a pair of positions with — two elements in the wrong order. The count measures how far an array is from sorted: 0 for sorted, for reversed. It is also the Kendall tau distance between two rankings: rank the same films by two people's preferences, write person B's ranking in person A's order, and count inversions.
Merge Sort & Inversion Counting proves this in full; here is the idea in divide-and-conquer terms. Recursively sort and count each half. While merging the two sorted halves, every time an element from the right half is placed before some elements still waiting in the left half, it forms an inversion with each of them — they are all larger than it (the left half is sorted, and the waiting ones are the largest), and they all came before it in the original array. So add "number of left elements still waiting" in one step.
Trace on [5, 3, 8, 6, 1, 4]. The split is [5, 3, 8] | [6, 1, 4], then [5] | [3, 8] and [6] | [1, 4].
| Step | Merge | Right element placed early | Left elements still waiting | Cross count | Running total |
|---|---|---|---|---|---|
| 1 | [3] with [8] | — | — | 0 | 0 |
| 2 | [5] with [3, 8] | 3 | [5] | 1 | 1 |
| 3 | [1] with [4] | — | — | 0 | 1 |
| 4 | [6] with [1, 4] | 1, then 4 | [6], [6] | 1 + 1 = 2 | 3 |
| 5 | [3, 5, 8] with [1, 4, 6] | 1 | [3, 5, 8] | 3 | 6 |
| 4 | [5, 8] | 2 | 8 | ||
| 6 | [8] | 1 | 9 |
Check by listing them: (5,3), (5,1), (5,4), (3,1), (8,6), (8,1), (8,4), (6,1), (6,4) — nine. The final merge found six of them with three additions.
Ties are not inversions
When left[i] == right[j], take the left element first (<=, not <). Otherwise a right element equal to waiting left elements is counted as inverted with them. [2, 2, 1] has 2 inversions, not 3.
2. Closest pair of points
Given points in the plane, find the two that are closest together. Brute force measures all pairs. Shamos and Hoey's divide and conquer does it in .
Divide. Sort the points by once. Split at the middle point: a vertical line with half the points on each side.
Conquer. Find the closest pair in the left half () and in the right half (). Let .
Combine. The answer is unless some pair with one point on each side is closer than . Such a pair must have both points within distance of the dividing line — any point farther away is already more than from everything on the other side. So collect the points in the strip and sort them by . Then, for each strip point, compare it only with the strip points just above it, stopping as soon as the -gap reaches . That loop does at most 7 comparisons per point (proved below), so the combine step is linear.
flowchart LR
S["Points sorted by x"] --> SPLIT["Split at median x"]
SPLIT --> L["Left half: delta L"]
SPLIT --> R["Right half: delta R"]
L --> D["delta = min of both"]
R --> D
D --> STRIP["Strip: points with x within delta of the line, sorted by y"]
STRIP --> SCAN["Each point vs the next few above it, stop when y gap reaches delta"]
SCAN --> ANS["Answer: min of delta and best strip pair"]
Getting the strip sorted by cheaply. Sorting the strip from scratch at every level costs per level and gives overall. The standard fix copies merge sort: make each recursive call return its points sorted by , and merge the two halves' -orders in linear time during the combine step. Then the strip is just a filter of an already-sorted list. (Remember the dividing before the recursion re-sorts the subarray by ; the reference code reads mid_x first for this reason.)
Trace. Eight points, already sorted by :
(0,10) (1,7) (4,8) (7,0) | (8,0) (10,2) (12,6) (13,8)
The code below works with squared distances (integers, no square roots), so is shown.
| Step | Subproblem | What happens | Best |
|---|---|---|---|
| 1 | (0,10) (1,7) | base case: one pair, | 10 |
| 2 | (4,8) (7,0) | base case: | 73 |
| 3 | left four, line | ; strip () by : (7,0) (1,7) (4,8); only (1,7)–(4,8) has -gap: distance = 10 | 10 |
| 4 | (8,0) (10,2) | base case: | 8 |
| 5 | (12,6) (13,8) | base case: | 5 |
| 6 | right four, line | ; strip: (10,2) (12,6) (13,8); (12,6)–(13,8) = 5, no improvement | 5 |
| 7 | all eight, line | ; strip () by : (7,0) (8,0) (10,2) | 5 |
| 8 | strip scan | (7,0)–(8,0): -gap 0, distance = 1. Next, (7,0)–(10,2): -gap = 4 ≥ 1, stop. (8,0)–(10,2): 4 ≥ 1, stop | 1 |
The answer, distance 1 between and , is a cross pair. Neither half could see it, and the strip found it with one comparison. Notice step 8 stops early: once shrinks, the strip loop gets even shorter.
Why at most 7 comparisons: the packing argument. Fix a strip point . The loop compares only with strip points above it with . All such points lie in a rectangle tall and wide, centred on the dividing line, with on its bottom edge.
flowchart TB
subgraph RECT["Rectangle: 2 delta wide, delta tall, above p"]
direction LR
LSQ["Left square: delta by delta, holds at most 4 left points"]
RSQ["Right square: delta by delta, holds at most 4 right points"]
end
Split the rectangle into its left and right squares. Every point in the left square belongs to the left half, and any two left-half points are at least apart. How many points can you place in a square with every pair at least apart? At most 4: cut the square into four quarters; two points in the same quarter would be at most apart, so each quarter holds at most one point. (Four is reachable: the four corners.) The same holds for the right square. So the rectangle contains at most points, one of which is itself — at most 7 others, and since they are the next points above in -order, the loop examines at most 7 before the -gap reaches . (This is the argument in CLRS §33.4. Points exactly on the dividing line can belong to either half, but each belongs to exactly one, so the count still holds. Tighter analyses bring the bound down — some textbooks say 5 or 6 — but any constant gives a linear combine.)
The constant is what matters. Without it, the strip could in principle hold all points and the combine step would be quadratic. The packing argument says the points cannot be crowded near the line and far apart from each other at the same time.
3. Karatsuba multiplication
Schoolbook multiplication of two -digit numbers multiplies every digit by every digit: digit products. Split each number into a high half and a low half of digits:
That needs four half-size products — , , , — and . No gain. Karatsuba's observation is that you do not need and separately, only their sum, and
You already have and . So three products suffice: , and , plus a few additions and subtractions, which cost . Now .
Worked example: . With : , , , .
| Step | Computation | Value |
|---|---|---|
| 1 | 672 | |
| 2 | 2,652 | |
| 3 | 6,164 | |
| 4 | 2,840 | |
| 5 | 6,720,000 + 284,000 + 2,652 = 7,006,652 |
Check: . (Directly, . ✔) Each of the three products in steps 1–3 is itself a two-digit (or, for , slightly larger) multiplication, which Karatsuba would split again. All the way down to single digits, an -digit product costs single-digit products instead of :
| Digits | Schoolbook () | Karatsuba () | Ratio |
|---|---|---|---|
| 2 | 4 | 3 | 1.3 |
| 16 | 256 | 81 | 3.2 |
| 128 | 16,384 | 2,187 | 7.5 |
| 1,024 | 1,048,576 | 59,049 | 17.8 |
The additions are not free, so for small numbers schoolbook wins. Real libraries switch to Karatsuba above a measured threshold: CPython's integers use it above 70 "digits" of 30 bits each (KARATSUBA_CUTOFF in Objects/longobject.c); Java's BigInteger above 80 32-bit words, switching again to Toom–Cook 3-way above 240 (KARATSUBA_THRESHOLD, TOOM_COOK_THRESHOLD in BigInteger.java); GMP tunes a sequence of thresholds per CPU, ending in FFT-based multiplication.
Split on bits, not decimal digits
The worked example splits in base 10 because it is easy to check by hand. Computers split in base or , or on bits: and , with shifts in place of multiplications by . The Python, Java and TypeScript implementations below do exactly that on built-in big integers; the C++ one, with no built-in big integer, works on vectors of decimal digits so you can see the base-10 version run.
Deeper: beyond Karatsuba
Split into three parts instead of two and you can get away with 5 products instead of 9 (Toom–Cook 3-way, ). The limit of that idea is the FFT: evaluate both numbers as polynomials at roots of unity, multiply pointwise, interpolate back. Schönhage and Strassen (1971) reached ; Harvey and van der Hoeven (2019, published in Annals of Mathematics in 2021) reached , believed optimal — though only for astronomically large . FFT is covered in FFT & NTT.
4. Strassen's matrix multiplication (intuition)
Multiplying two matrices by the definition takes scalar multiplications. Split each matrix into four blocks:
That is 8 block products: . Again, splitting alone gains nothing. Strassen found 7 products that suffice:
You do not need to memorise these. Check them once on numbers: with and , the seven products are , , , , , , , giving , , , — the same as computed directly. The point is the count: 7 recursive products and 18 block additions/subtractions, so
For fully recursed, that is scalar multiplications instead of — 3.8 times fewer.
Why it is rarely used in practice. The numerical libraries under NumPy, MATLAB and PyTorch (BLAS implementations such as OpenBLAS, Intel MKL and cuBLAS) use the plain algorithm, carefully blocked for caches and vector units. Reasons:
- The crossover is high. The 18 extra additions and the temporary blocks cost memory traffic. Strassen beats a tuned kernel only for matrices of roughly a thousand rows or more, and the gain at practical sizes is tens of percent, not factors. Measured crossovers vary widely with the hardware (Huang, Smith, Henry and van de Geijn, "Strassen's Algorithm Reloaded", SC16, report practical speed-ups with careful implementation).
- Numerical stability is weaker. In floating point, Strassen's error bound depends on the norms of whole matrices rather than on each entry's own products, so it can be noticeably less accurate on badly scaled inputs (Higham, Accuracy and Stability of Numerical Algorithms, §23).
- Memory and structure. It needs extra workspace, prefers power-of-two sizes, and does not help sparse or structured matrices.
- Hardware favours regular work. GPUs and SIMD units are built to do huge numbers of multiply–adds in a regular pattern; trading multiplications for irregular additions is a poor deal there.
It is used where exact arithmetic makes multiplications expensive (big integers, finite fields) and in some specialised libraries. The theoretical exponent of matrix multiplication has been pushed far lower — below 2.372 by 2024, through work starting with Coppersmith and Winograd (1990) — but those algorithms have constants so large they are never run ("galactic algorithms").
5. Maximum subarray: divide and conquer vs Kadane
Find the contiguous subarray with the largest sum. For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the answer is 6, from [4, -1, 2, 1].
Divide and conquer. The best subarray lies entirely in the left half, entirely in the right half, or crosses the middle. The first two are recursive calls. A crossing subarray is a suffix of the left half glued to a prefix of the right half, and the two parts can be chosen independently: take the best suffix ending at the middle (scan left from the middle) plus the best prefix starting at the middle (scan right). combine, so .
Top level of the example: split into [-2, 1, -3, 4] and [-1, 2, 1, -5, 4].
| Part | How | Value |
|---|---|---|
| Best in left half | recursion | 4 ([4]) |
| Best in right half | recursion | 4 ([4] at the end, beating [2, 1] = 3) |
| Best suffix of left | scanning left from the middle: 4, 1, 2, 0 | 4 |
| Best prefix of right | scanning right from the middle: −1, 1, 2, −3, 1 | 2 |
| Crossing | 4 + 2 | 6 |
| Answer | max(4, 4, 6) | 6 |
Kadane's algorithm (, one pass): keep the best sum of a subarray ending at the current position; it is either the current element alone or the current element added to the best run ending just before it: cur = max(v, cur + v). The answer is the largest cur ever seen. Kadane is really a one-dimensional DP.
Which to use? Kadane, almost always: shorter, , memory. The divide-and-conquer version is worth knowing for two reasons. First, it can be made too, by having each call return four numbers — total sum, best prefix, best suffix, best overall — so the combine step is : , , and so on. Second, those four numbers are exactly what a segment tree node stores to answer "maximum subarray sum in " queries with point updates — something Kadane cannot do. Divide and conquer turns into a data structure.
6. Fast exponentiation
Compute . The obvious loop does multiplications. Instead use
One recursive call on half the exponent plus one or two multiplications: multiplications. This is decrease and conquer — a single subproblem — and it is also the reason to not write pow(x, n/2) * pow(x, n/2): two identical calls make it again.
Trace for (13 is binary 1101):
| Call | Exponent | Rule | Result |
|---|---|---|---|
| 1 | 0 | base | 1 |
| 2 | 1 | odd: | 3 |
| 3 | 3 | odd: | 27 |
| 4 | 6 | even: | 729 |
| 5 | 13 | odd: | 1,594,323 |
Seven multiplications instead of twelve; for , about 120 instead of . The same recursion works for anything with an associative multiplication: modular powers in RSA and Diffie–Hellman, matrix powers for Fibonacci and linear recurrences (Matrix Exponentiation), composing permutations, and "binary lifting" on trees (LCA & Binary Lifting).
7. Quickselect: conquer only one side
To find the -th smallest element, partition around a pivot as in quicksort, then recurse only into the side that contains position . With a random pivot the expected sizes shrink geometrically, , so the expected time is ; the worst case is , and the median-of-medians pivot (Blum, Floyd, Pratt, Rivest and Tarjan, 1973) makes it worst-case. Full treatment, code and proofs: Quickselect & Order Statistics. It is the decrease-and-conquer cousin of quicksort, just as binary search is the cousin of merge sort.
The ladder: brute force → better → optimal
Counting inversions.
| Rung | Idea | Time | Space | Why better |
|---|---|---|---|---|
| 1 | Check every pair | — the baseline and the test oracle | ||
| 2 | Insertion sort, counting swaps (each swap removes exactly one inversion) | , = inversions | Fast for nearly sorted input; still worst case | |
| 3 | Merge sort, count cross pairs while merging | Cross pairs counted in bulk | ||
| 3′ | Fenwick tree over compressed values: for each element, count earlier elements greater than it | Same bound; online (works as elements stream in) |
Closest pair.
| Rung | Idea | Time | Why better |
|---|---|---|---|
| 1 | Every pair | baseline | |
| 2 | Sort by , sweep, and skip pairs whose -gap already exceeds the best | worst case, fast on random data | prunes, but no guarantee |
| 3 | Divide and conquer, sorting the strip at every level | packing argument makes the strip scan linear | |
| 4 | Divide and conquer, merging by | removes the per-level sort; optimal in the algebraic decision-tree model (it can decide element distinctness, which needs there) | |
| alt | Randomized grid hashing (Rabin 1976; Khuller and Matias 1995) | expected | uses hashing and the floor function, outside the comparison model |
Multiplying -digit numbers.
| Rung | Idea | Time | Notes |
|---|---|---|---|
| 1 | Repeated addition | absurd, but correct | |
| 2 | Schoolbook | best below a few dozen machine words | |
| 3 | Karatsuba | 3 products instead of 4 | |
| 4 | Toom–Cook -way | more pieces, fewer relative products | |
| 5 | FFT (Schönhage–Strassen; Harvey–van der Hoeven) | ; | huge numbers only |
Maximum subarray: all subarrays with nested sums → with prefix sums → divide and conquer → four-value divide and conquer or Kadane .
Correctness
Every divide-and-conquer proof is strong induction on the input size: assume the recursive calls are correct on all smaller inputs (they are smaller because each piece has size at most for ); check the base case directly; then prove the combine step turns correct sub-answers into a correct answer. Only the combine step needs real thought.
Inversion counting. Every inversion is inside , inside , or a cross pair; the three sets are disjoint. By induction the recursive calls count the first two and return sorted halves. For the cross pairs: consider the moment the merge outputs a right element . The left elements not yet output are exactly the left elements greater than (with <= tie-breaking, an equal left element would have been output first), and every one of them was before in the original array. So adding their number counts exactly the cross inversions involving , and each cross inversion is counted once, at the moment its right element is output.
Closest pair. Let be a closest pair. If both are on the same side, the recursive call found a pair at distance . Otherwise (or the answer is already ), so both are within of the line in and within of each other in , so both are in the strip, and whichever is lower in -order meets the other before the scan's -gap reaches . Hence the scan examines the pair. The packing argument is only needed for the running time, not for correctness: the code's loop stops on the -gap, never on a count of 7.
Karatsuba. Pure algebra: and . By induction the three recursive products are correct: above the cutoff, each of their operands has roughly half as many bits as the larger input (plus one carry bit for ), so they are strictly smaller instances. Hence the result is correct.
Maximum subarray. The optimal subarray is in , in , or crosses the middle; the three cases are exhaustive. A crossing subarray is (suffix of ending at the middle) + (prefix of starting at the middle), and its sum is the sum of the two parts, which can be maximised independently. So the max of the three candidates is the optimum.
Fast exponentiation. and , by the laws of exponents (any associative multiplication).
Complexity
| Algorithm | Time | Extra space | Recursion depth |
|---|---|---|---|
| Inversion count (merge sort) | best, average and worst | buffer | |
| Closest pair | (initial sort + ) | ||
| Karatsuba | digit operations | per level, total with care | |
| Strassen | |||
| Max subarray (simple D&C) | stack | ||
| Kadane | — | ||
| Fast exponentiation | multiplications | recursive, iterative | |
| Quickselect | expected, worst | iterative | — |
Space and the stack. Balanced splits give recursion depth — about 20 for a million elements, so stack overflow is not a concern. Unbalanced splits (quicksort on sorted input with a first-element pivot) give depth , which overflows. Recurse on the smaller side and loop on the larger one to cap depth at .
Constants. Recursion has overhead: a function call, slicing, allocation. Practical implementations stop recursing at a small size (16–64 elements, or a few machine words for multiplication) and switch to the simple quadratic method, which is faster there. Allocate one buffer up front and pass indices, instead of slicing arrays at every call (the implementations below do this).
Big numbers in the cost model. Karatsuba's bound counts digit operations. In the RAM model, multiplying two machine words is ; the analysis applies to numbers with many words.
Implementation
All three snippets per language are complete programs. Each checks the examples from this lesson and then runs 300 random tests against brute force: inversions against the pair count, closest pair against all pairs (with duplicate points), and Karatsuba against the language's own multiplication (Python, Java, TypeScript) or schoolbook digit multiplication (C++).
- Inversions: one buffer allocated once;
<=in the merge so ties are not counted. - Closest pair: squared integer distances (no floating-point error, no square roots); returns infinity for fewer than two points; reads the dividing before the recursive calls re-sort by .
- Karatsuba: Python, Java and TypeScript split built-in big integers on bits and fall back to the built-in product below 64 bits. C++ has no big integer, so it uses vectors of decimal digits, least significant first, with a schoolbook base case below 32 digits.
import random
from typing import List, Tuple
Point = Tuple[int, int]
# ---------- 1. Counting inversions (merge sort) ----------
def count_inversions(a: List[int]) -> int:
"""Number of pairs i < j with a[i] > a[j]. O(n log n)."""
a = list(a)
buf = [0] * len(a)
def sort(lo: int, hi: int) -> int: # sorts a[lo:hi], returns its inversions
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
inv = sort(lo, mid) + sort(mid, hi)
i, j, k = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]: # <= keeps equal values non-inverted
buf[k] = a[i]; i += 1
else:
buf[k] = a[j]; j += 1
inv += mid - i # a[j] jumps over every left item still waiting
k += 1
buf[k:hi] = a[i:mid] if i < mid else a[j:hi]
a[lo:hi] = buf[lo:hi]
return inv
return sort(0, len(a))
# ---------- 2. Closest pair of points ----------
INF = float("inf")
def dist2(p: Point, q: Point) -> int:
return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2
def closest_pair(points: List[Point]) -> int:
"""Smallest squared distance between two of the points (inf if fewer than 2). O(n log n)."""
a = sorted(points) # by x, then y
buf: List[Point] = [(0, 0)] * len(a)
def rec(lo: int, hi: int): # returns best in a[lo:hi]; leaves a[lo:hi] sorted by y
if hi - lo <= 3:
best = INF
for i in range(lo, hi):
for j in range(i + 1, hi):
best = min(best, dist2(a[i], a[j]))
a[lo:hi] = sorted(a[lo:hi], key=lambda p: p[1])
return best
mid = (lo + hi) // 2
mid_x = a[mid][0] # read before the recursion re-sorts by y
best = min(rec(lo, mid), rec(mid, hi))
# merge the two halves by y
i, j, k = lo, mid, lo
while i < mid or j < hi:
if j == hi or (i < mid and a[i][1] <= a[j][1]):
buf[k] = a[i]; i += 1
else:
buf[k] = a[j]; j += 1
k += 1
a[lo:hi] = buf[lo:hi]
# the strip: points closer than sqrt(best) to the dividing line, already in y order
strip = [p for p in a[lo:hi] if (p[0] - mid_x) ** 2 < best]
for s in range(len(strip)):
t = s + 1
while t < len(strip) and (strip[t][1] - strip[s][1]) ** 2 < best: # at most 7 iterations
best = min(best, dist2(strip[s], strip[t]))
t += 1
return best
return rec(0, len(a))
# ---------- 3. Karatsuba multiplication ----------
CUTOFF_BITS = 64
def karatsuba(x: int, y: int) -> int:
"""x * y for non-negative ints using 3 recursive products. O(n^1.585) digit operations."""
if x.bit_length() <= CUTOFF_BITS or y.bit_length() <= CUTOFF_BITS:
return x * y # small: machine-sized multiply
m = max(x.bit_length(), y.bit_length()) // 2
mask = (1 << m) - 1
a, b = x >> m, x & mask # x = a*2^m + b
c, d = y >> m, y & mask # y = c*2^m + d
ac = karatsuba(a, c)
bd = karatsuba(b, d)
mid = karatsuba(a + b, c + d) - ac - bd # = ad + bc, one multiplication instead of two
return (ac << (2 * m)) + (mid << m) + bd
def multiply(x: int, y: int) -> int:
sign = -1 if (x < 0) != (y < 0) else 1
return sign * karatsuba(abs(x), abs(y))
if __name__ == "__main__":
assert count_inversions([5, 3, 8, 6, 1, 4]) == 9
assert count_inversions([1, 2, 3]) == 0
assert count_inversions([3, 2, 1]) == 3
assert count_inversions([2, 2, 1]) == 2
assert count_inversions([]) == 0
pts = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
assert closest_pair(pts) == 2 # (2,3)-(3,4): sqrt(2)
assert closest_pair([(0, 0)]) == INF
assert closest_pair([(1, 1), (1, 1)]) == 0
assert multiply(1234, 5678) == 7006652
assert multiply(-(3 ** 200), 7 ** 150) == -(3 ** 200) * 7 ** 150
rng = random.Random(1)
for _ in range(300): # stress against brute force
n = rng.randint(0, 40)
arr = [rng.randint(0, 10) for _ in range(n)]
brute = sum(arr[i] > arr[j] for i in range(n) for j in range(i + 1, n))
assert count_inversions(arr) == brute
P = [(rng.randint(-30, 30), rng.randint(-30, 30)) for _ in range(n)]
brute = min((dist2(P[i], P[j]) for i in range(n) for j in range(i + 1, n)), default=INF)
assert closest_pair(P) == brute
x, y = rng.getrandbits(rng.randint(1, 3000)), rng.getrandbits(rng.randint(1, 3000))
assert karatsuba(x, y) == x * y
print("all divide-and-conquer tests passed")
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Random;
public class Main {
// ---------- 1. Counting inversions (merge sort) ----------
static long countInversions(int[] input) {
int[] a = input.clone();
int[] buf = new int[a.length];
return sortCount(a, buf, 0, a.length);
}
private static long sortCount(int[] a, int[] buf, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) >>> 1;
long inv = sortCount(a, buf, lo, mid) + sortCount(a, buf, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[i] <= a[j]) buf[k++] = a[i++];
else { buf[k++] = a[j++]; inv += mid - i; } // a[j] jumps over mid - i items
}
while (i < mid) buf[k++] = a[i++];
while (j < hi) buf[k++] = a[j++];
System.arraycopy(buf, lo, a, lo, hi - lo);
return inv;
}
// ---------- 2. Closest pair of points ----------
static final long INF = Long.MAX_VALUE;
static long dist2(long[] p, long[] q) {
long dx = p[0] - q[0], dy = p[1] - q[1];
return dx * dx + dy * dy;
}
/** Smallest squared distance between two points; INF if fewer than two. */
static long closestPair(long[][] points) {
long[][] a = points.clone();
Arrays.sort(a, (p, q) -> p[0] != q[0] ? Long.compare(p[0], q[0]) : Long.compare(p[1], q[1]));
return rec(a, new long[a.length][], 0, a.length);
}
private static long rec(long[][] a, long[][] buf, int lo, int hi) {
if (hi - lo <= 3) {
long best = INF;
for (int i = lo; i < hi; i++)
for (int j = i + 1; j < hi; j++) best = Math.min(best, dist2(a[i], a[j]));
Arrays.sort(a, lo, hi, (p, q) -> Long.compare(p[1], q[1]));
return best;
}
int mid = (lo + hi) >>> 1;
long midX = a[mid][0]; // read before recursion re-sorts by y
long best = Math.min(rec(a, buf, lo, mid), rec(a, buf, mid, hi));
int i = lo, j = mid, k = lo; // merge halves by y
while (i < mid || j < hi) {
if (j == hi || (i < mid && a[i][1] <= a[j][1])) buf[k++] = a[i++];
else buf[k++] = a[j++];
}
System.arraycopy(buf, lo, a, lo, hi - lo);
long[][] strip = new long[hi - lo][];
int m = 0;
for (int t = lo; t < hi; t++) {
long dx = a[t][0] - midX;
if (dx * dx < best) strip[m++] = a[t];
}
for (int s = 0; s < m; s++) {
for (int t = s + 1; t < m; t++) { // at most 7 iterations per s
long dy = strip[t][1] - strip[s][1];
if (dy * dy >= best) break;
best = Math.min(best, dist2(strip[s], strip[t]));
}
}
return best;
}
// ---------- 3. Karatsuba multiplication (BigInteger, split on bits) ----------
static final int CUTOFF_BITS = 64;
static BigInteger karatsuba(BigInteger x, BigInteger y) {
if (x.signum() < 0 || y.signum() < 0) {
BigInteger p = karatsuba(x.abs(), y.abs());
return x.signum() * y.signum() < 0 ? p.negate() : p;
}
if (x.bitLength() <= CUTOFF_BITS || y.bitLength() <= CUTOFF_BITS) return x.multiply(y);
int m = Math.max(x.bitLength(), y.bitLength()) / 2;
BigInteger a = x.shiftRight(m), b = x.subtract(a.shiftLeft(m)); // x = a*2^m + b
BigInteger c = y.shiftRight(m), d = y.subtract(c.shiftLeft(m)); // y = c*2^m + d
BigInteger ac = karatsuba(a, c);
BigInteger bd = karatsuba(b, d);
BigInteger mid = karatsuba(a.add(b), c.add(d)).subtract(ac).subtract(bd); // ad + bc
return ac.shiftLeft(2 * m).add(mid.shiftLeft(m)).add(bd);
}
public static void main(String[] args) {
if (countInversions(new int[]{5, 3, 8, 6, 1, 4}) != 9) throw new AssertionError();
if (countInversions(new int[]{2, 2, 1}) != 2) throw new AssertionError();
if (countInversions(new int[]{}) != 0) throw new AssertionError();
long[][] pts = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
if (closestPair(pts) != 2) throw new AssertionError();
if (closestPair(new long[][]{{0, 0}}) != INF) throw new AssertionError();
if (!karatsuba(BigInteger.valueOf(1234), BigInteger.valueOf(5678)).equals(BigInteger.valueOf(7006652)))
throw new AssertionError();
Random rng = new Random(1);
for (int iter = 0; iter < 300; iter++) { // stress against brute force
int n = rng.nextInt(41);
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = rng.nextInt(11);
long brute = 0;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (arr[i] > arr[j]) brute++;
if (countInversions(arr) != brute) throw new AssertionError("inversions");
long[][] p = new long[n][];
for (int i = 0; i < n; i++) p[i] = new long[]{rng.nextInt(61) - 30, rng.nextInt(61) - 30};
long best = INF;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) best = Math.min(best, dist2(p[i], p[j]));
if (closestPair(p) != best) throw new AssertionError("closest pair");
BigInteger x = new BigInteger(1 + rng.nextInt(3000), rng);
BigInteger y = new BigInteger(1 + rng.nextInt(3000), rng);
if (rng.nextBoolean()) x = x.negate();
if (!karatsuba(x, y).equals(x.multiply(y))) throw new AssertionError("karatsuba");
}
System.out.println("all divide-and-conquer tests passed");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <random>
#include <string>
#include <utility>
#include <vector>
// ---------- 1. Counting inversions (merge sort) ----------
long long sortCount(std::vector<int>& a, std::vector<int>& buf, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = lo + (hi - lo) / 2;
long long inv = sortCount(a, buf, lo, mid) + sortCount(a, buf, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[i] <= a[j]) buf[k++] = a[i++];
else { buf[k++] = a[j++]; inv += mid - i; } // a[j] jumps over mid - i items
}
while (i < mid) buf[k++] = a[i++];
while (j < hi) buf[k++] = a[j++];
std::copy(buf.begin() + lo, buf.begin() + hi, a.begin() + lo);
return inv;
}
long long countInversions(std::vector<int> a) {
std::vector<int> buf(a.size());
return sortCount(a, buf, 0, (int)a.size());
}
// ---------- 2. Closest pair of points ----------
using Pt = std::pair<long long, long long>; // (x, y)
const long long INF = std::numeric_limits<long long>::max();
long long dist2(const Pt& p, const Pt& q) {
long long dx = p.first - q.first, dy = p.second - q.second;
return dx * dx + dy * dy;
}
long long rec(std::vector<Pt>& a, std::vector<Pt>& buf, int lo, int hi) {
auto byY = [](const Pt& p, const Pt& q) { return p.second < q.second; };
if (hi - lo <= 3) {
long long best = INF;
for (int i = lo; i < hi; i++)
for (int j = i + 1; j < hi; j++) best = std::min(best, dist2(a[i], a[j]));
std::sort(a.begin() + lo, a.begin() + hi, byY);
return best;
}
int mid = lo + (hi - lo) / 2;
long long midX = a[mid].first; // read before recursion re-sorts by y
long long best = std::min(rec(a, buf, lo, mid), rec(a, buf, mid, hi));
std::merge(a.begin() + lo, a.begin() + mid, a.begin() + mid, a.begin() + hi,
buf.begin() + lo, byY);
std::copy(buf.begin() + lo, buf.begin() + hi, a.begin() + lo);
std::vector<Pt> strip;
for (int t = lo; t < hi; t++) {
long long dx = a[t].first - midX;
if (dx * dx < best) strip.push_back(a[t]);
}
for (size_t s = 0; s < strip.size(); s++) {
for (size_t t = s + 1; t < strip.size(); t++) { // at most 7 iterations per s
long long dy = strip[t].second - strip[s].second;
if (dy * dy >= best) break;
best = std::min(best, dist2(strip[s], strip[t]));
}
}
return best;
}
long long closestPair(std::vector<Pt> a) {
std::sort(a.begin(), a.end()); // by x, then y
std::vector<Pt> buf(a.size());
return rec(a, buf, 0, (int)a.size());
}
// ---------- 3. Karatsuba on decimal digit strings ----------
// Numbers are vectors of base-10 digits, least significant first.
using Digits = std::vector<int>;
void trim(Digits& v) { while (v.size() > 1 && v.back() == 0) v.pop_back(); }
Digits schoolbook(const Digits& x, const Digits& y) {
std::vector<long long> r(x.size() + y.size(), 0);
for (size_t i = 0; i < x.size(); i++)
for (size_t j = 0; j < y.size(); j++) r[i + j] += (long long)x[i] * y[j];
Digits out(r.size());
long long carry = 0;
for (size_t i = 0; i < r.size(); i++) { long long v = r[i] + carry; out[i] = (int)(v % 10); carry = v / 10; }
trim(out);
return out;
}
Digits add(const Digits& x, const Digits& y) {
Digits r(std::max(x.size(), y.size()) + 1, 0);
int carry = 0;
for (size_t i = 0; i < r.size(); i++) {
int v = carry + (i < x.size() ? x[i] : 0) + (i < y.size() ? y[i] : 0);
r[i] = v % 10; carry = v / 10;
}
trim(r);
return r;
}
Digits sub(const Digits& x, const Digits& y) { // requires x >= y
Digits r(x);
int borrow = 0;
for (size_t i = 0; i < r.size(); i++) {
int v = r[i] - borrow - (i < y.size() ? y[i] : 0);
borrow = v < 0;
r[i] = v + (borrow ? 10 : 0);
}
trim(r);
return r;
}
Digits shift(const Digits& x, size_t k) { // x * 10^k
if (x.size() == 1 && x[0] == 0) return x;
Digits r(k, 0);
r.insert(r.end(), x.begin(), x.end());
return r;
}
Digits karatsuba(const Digits& x, const Digits& y) {
if (x.size() < 32 || y.size() < 32) return schoolbook(x, y);
size_t m = std::max(x.size(), y.size()) / 2;
auto low = [&](const Digits& v) { Digits r(v.begin(), v.begin() + std::min(m, v.size())); trim(r); return r; };
auto high = [&](const Digits& v) { if (v.size() <= m) return Digits{0}; Digits r(v.begin() + m, v.end()); trim(r); return r; };
Digits a = high(x), b = low(x), c = high(y), d = low(y); // x = a*10^m + b, y = c*10^m + d
Digits ac = karatsuba(a, c);
Digits bd = karatsuba(b, d);
Digits mid = sub(sub(karatsuba(add(a, b), add(c, d)), ac), bd); // ad + bc
return add(add(shift(ac, 2 * m), shift(mid, m)), bd);
}
Digits fromString(const std::string& s) {
Digits d;
for (auto it = s.rbegin(); it != s.rend(); ++it) d.push_back(*it - '0');
trim(d);
return d;
}
std::string toString(const Digits& d) {
std::string s;
for (auto it = d.rbegin(); it != d.rend(); ++it) s.push_back(char('0' + *it));
return s;
}
std::string multiply(const std::string& x, const std::string& y) {
return toString(karatsuba(fromString(x), fromString(y)));
}
int main() {
assert(countInversions({5, 3, 8, 6, 1, 4}) == 9);
assert(countInversions({2, 2, 1}) == 2);
assert(countInversions({}) == 0);
assert(closestPair({{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}) == 2);
assert(closestPair({{0, 0}}) == INF);
assert(multiply("1234", "5678") == "7006652");
// 2^200 = 1606938044258990275541962092341162602522202993782792835301376
std::string p100 = "1267650600228229401496703205376"; // 2^100
assert(multiply(p100, p100) == "1606938044258990275541962092341162602522202993782792835301376");
std::mt19937 rng(1);
auto rnd = [&](int lo, int hi) { return std::uniform_int_distribution<int>(lo, hi)(rng); };
for (int iter = 0; iter < 300; iter++) { // stress against brute force
int n = rnd(0, 40);
std::vector<int> arr(n);
for (int& v : arr) v = rnd(0, 10);
long long brute = 0;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) brute += arr[i] > arr[j];
assert(countInversions(arr) == brute);
std::vector<Pt> p(n);
for (auto& q : p) q = {rnd(-30, 30), rnd(-30, 30)};
long long best = INF;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) best = std::min(best, dist2(p[i], p[j]));
assert(closestPair(p) == best);
std::string x(rnd(1, 400), '0'), y(rnd(1, 400), '0');
for (char& ch : x) ch = char('0' + rnd(0, 9));
for (char& ch : y) ch = char('0' + rnd(0, 9));
assert(karatsuba(fromString(x), fromString(y)) == schoolbook(fromString(x), fromString(y)));
}
std::cout << "all divide-and-conquer tests passed\n";
}
// ---------- 1. Counting inversions (merge sort) ----------
function countInversions(input: number[]): number {
const a = input.slice();
const buf = new Array<number>(a.length);
function sort(lo: number, hi: number): number {
if (hi - lo <= 1) return 0;
const mid = (lo + hi) >> 1;
let inv = sort(lo, mid) + sort(mid, hi);
let i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[i] <= a[j]) buf[k++] = a[i++];
else { buf[k++] = a[j++]; inv += mid - i; } // a[j] jumps over mid - i items
}
while (i < mid) buf[k++] = a[i++];
while (j < hi) buf[k++] = a[j++];
for (let t = lo; t < hi; t++) a[t] = buf[t];
return inv;
}
return sort(0, a.length);
}
// ---------- 2. Closest pair of points ----------
type Point = [number, number];
function dist2(p: Point, q: Point): number {
const dx = p[0] - q[0], dy = p[1] - q[1];
return dx * dx + dy * dy;
}
/** Smallest squared distance between two points; Infinity if fewer than two. */
function closestPair(points: Point[]): number {
const a = points.slice().sort((p, q) => p[0] - q[0] || p[1] - q[1]);
const buf = new Array<Point>(a.length);
function rec(lo: number, hi: number): number {
if (hi - lo <= 3) {
let best = Infinity;
for (let i = lo; i < hi; i++)
for (let j = i + 1; j < hi; j++) best = Math.min(best, dist2(a[i], a[j]));
const part = a.slice(lo, hi).sort((p, q) => p[1] - q[1]);
for (let t = lo; t < hi; t++) a[t] = part[t - lo];
return best;
}
const mid = (lo + hi) >> 1;
const midX = a[mid][0]; // read before recursion re-sorts by y
let best = Math.min(rec(lo, mid), rec(mid, hi));
let i = lo, j = mid, k = lo; // merge halves by y
while (i < mid || j < hi) {
if (j === hi || (i < mid && a[i][1] <= a[j][1])) buf[k++] = a[i++];
else buf[k++] = a[j++];
}
for (let t = lo; t < hi; t++) a[t] = buf[t];
const strip: Point[] = [];
for (let t = lo; t < hi; t++) if ((a[t][0] - midX) ** 2 < best) strip.push(a[t]);
for (let s = 0; s < strip.length; s++) {
for (let t = s + 1; t < strip.length; t++) { // at most 7 iterations per s
if ((strip[t][1] - strip[s][1]) ** 2 >= best) break;
best = Math.min(best, dist2(strip[s], strip[t]));
}
}
return best;
}
return rec(0, a.length);
}
// ---------- 3. Karatsuba multiplication (bigint, split on bits) ----------
const CUTOFF_BITS = 64;
function bitLength(x: bigint): number {
return x === 0n ? 0 : x.toString(2).length;
}
function karatsuba(x: bigint, y: bigint): bigint {
if (x < 0n || y < 0n) {
const p = karatsuba(x < 0n ? -x : x, y < 0n ? -y : y);
return (x < 0n) !== (y < 0n) ? -p : p;
}
const bx = bitLength(x), by = bitLength(y);
if (bx <= CUTOFF_BITS || by <= CUTOFF_BITS) return x * y;
const m = BigInt(Math.floor(Math.max(bx, by) / 2));
const mask = (1n << m) - 1n;
const a = x >> m, b = x & mask; // x = a*2^m + b
const c = y >> m, d = y & mask; // y = c*2^m + d
const ac = karatsuba(a, c);
const bd = karatsuba(b, d);
const mid = karatsuba(a + b, c + d) - ac - bd; // ad + bc
return (ac << (2n * m)) + (mid << m) + bd;
}
// ---------- tests ----------
function assert(cond: boolean, msg = "assertion failed"): void {
if (!cond) throw new Error(msg);
}
assert(countInversions([5, 3, 8, 6, 1, 4]) === 9);
assert(countInversions([2, 2, 1]) === 2);
assert(countInversions([]) === 0);
assert(closestPair([[2, 3], [12, 30], [40, 50], [5, 1], [12, 10], [3, 4]]) === 2);
assert(closestPair([[0, 0]]) === Infinity);
assert(karatsuba(1234n, 5678n) === 7006652n);
assert(karatsuba(-(3n ** 200n), 7n ** 150n) === -(3n ** 200n) * 7n ** 150n);
let seed = 1;
function rnd(lo: number, hi: number): number { // small LCG, deterministic
seed = (seed * 48271) % 2147483647;
return lo + (seed % (hi - lo + 1));
}
function randomBig(bits: number): bigint {
let s = "";
for (let i = 0; i < bits; i++) s += rnd(0, 1);
return BigInt("0b" + s);
}
for (let iter = 0; iter < 300; iter++) { // stress against brute force
const n = rnd(0, 40);
const arr = Array.from({ length: n }, () => rnd(0, 10));
let brute = 0;
for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (arr[i] > arr[j]) brute++;
assert(countInversions(arr) === brute, "inversions");
const p: Point[] = Array.from({ length: n }, () => [rnd(-30, 30), rnd(-30, 30)] as Point);
let best = Infinity;
for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) best = Math.min(best, dist2(p[i], p[j]));
assert(closestPair(p) === best, "closest pair");
const x = randomBig(rnd(1, 2000)), y = randomBig(rnd(1, 2000));
assert(karatsuba(x, y) === x * y, "karatsuba");
}
console.log("all divide-and-conquer tests passed");
Real-world uses
- Sorting everywhere. Merge sort's merge step is the core of Timsort (Python's
sorted, Java'sArrays.sortfor objects, V8'sArray.prototype.sort) and of external sorting in databases, where runs too big for memory are sorted and merged from disk. See Sorting in the Real World. - Big-integer arithmetic. CPython, Java's
BigIntegerand GMP all switch from schoolbook to Karatsuba (and then Toom–Cook and FFT) at tuned thresholds. Every RSA key generation, every arbitrary-precision computation of and every cryptographic library that multiplies 2048-bit numbers runs this code. - Signal processing. The Cooley–Tukey FFT is divide and conquer on the indices of the input. It is in audio codecs (MP3, AAC), image compression (JPEG uses the closely related DCT), Wi-Fi and 4G/5G modulation (OFDM), and fast polynomial multiplication.
- Ranking and recommendation. Inversion counts give the Kendall tau distance between rankings, used to compare search-engine result orders, evaluate recommendation systems and aggregate votes (Kleinberg and Tardos, §5.3, use exactly this motivation).
- Computational geometry and GIS. Closest-pair and related divide-and-conquer algorithms (convex hull, Voronoi diagrams via Fortune's sweep or D&C, k-d tree construction by median splits) underlie spatial databases and collision detection; see Spatial Trees and spatial indexing.
- Parallel and distributed computing. Divide-and-conquer recursion maps naturally onto fork/join parallelism (Java's
ForkJoinPooland parallel streams, Intel TBB, Cilk) and onto MapReduce, where "map" processes independent chunks and "reduce" combines them. - Cache-oblivious algorithms. Recursive matrix multiplication and transposition, which split until blocks fit in cache without knowing the cache size, are a direct application (Frigo, Leiserson, Prokop and Ramachandran, 1999).
- Debugging.
git bisectfinds the commit that introduced a bug by binary search over history — decrease and conquer on a sequence of commits.
Pitfalls & edge cases
- Forgetting the base case, or a base case that never triggers. Splitting at
mid = (lo + hi) // 2with base casehi - lo <= 1always terminates; a base case oflo == hiwith closed intervals can loop forever on two elements. - Uneven or empty splits. For odd the halves differ by one; make sure no call receives an empty range unless the code handles it (closest pair returns infinity for fewer than two points).
- Integer overflow. Inversion counts reach for — use 64-bit. Squared distances of coordinates up to reach , just inside signed 64-bit; beyond that use 128-bit or floating point.
mid = (lo + hi) / 2overflows 32-bit indices near ; uselo + (hi - lo) / 2or>>>. - Ties in the merge.
<instead of<=counts equal elements as inversions. - Closest pair: reading the dividing after the recursion. If the recursive calls re-sort their ranges by ,
a[mid].xis no longer the median . Save it first. - Closest pair: using instead of in the strip test. Harmless for correctness, but it puts more points in the strip for no benefit: a point exactly from the line cannot beat .
- Closest pair with floating-point coordinates. Compare squared distances to avoid
sqrt, and be careful with exact ties near the line. - Karatsuba: the middle term can have one more digit. and may carry into an extra digit; your split must handle operands of unequal length.
- Karatsuba: negative numbers. Multiply magnitudes and fix the sign at the end, or the bit-splitting breaks (shifts of negative numbers round toward minus infinity).
- Recursing to size 1. Correct, but slow: allocation and call overhead dominate. Use a cutoff.
- Calling the same subproblem twice.
pow(x, n//2) * pow(x, n//2)is . If two branches can reach the same subproblem, you need memoization (DP), not divide and conquer. - Copying slices at every level.
merge_sort(a[:mid])in Python allocates per level — fine asymptotically, but several times slower than passing indices and one shared buffer.
Variations
- Decrease and conquer. One subproblem: binary search, fast exponentiation, quickselect, Euclid's GCD,
git bisect. - Divide and conquer on the answer. Binary search over a monotone predicate ("can we finish with capacity ?") — see Binary Search.
- CDQ divide and conquer (offline). Split a sequence of updates and queries in time; let the first half's updates answer the second half's queries in a merge-like pass. Solves 3-D dominance counting and dynamic problems offline in . Named after Chen Danqi, who popularised it in Chinese competitive programming.
- Divide and conquer on trees. Centroid decomposition splits a tree at a vertex whose removal leaves pieces of at most half the size, giving levels — see Heavy-Light & Centroid Decomposition.
- Divide and conquer DP optimisation. When the best split point of a DP row is monotone, compute the row by recursively solving the middle position first: instead of — see DP Optimizations.
- Merge-sort tree. Keep every merge sort level's sorted lists as a segment tree to answer "how many values in " in .
- Meet in the middle. Split a set of items into two halves, enumerate each half's subsets, and combine with sorting or hashing: instead of for subset sum with . A divide-and-conquer idea applied to brute force.
- Polynomial and FFT-based algorithms. Multiplying polynomials, big integers and convolutions with FFT/NTT; see FFT & NTT.
- Parallel divide and conquer. The two recursive calls are independent, so run them on different cores. Merge sort's span (longest chain of dependent work) becomes with a sequential merge, or with a parallel merge; see Parallel Algorithms.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Pow(x, n) (LeetCode 50) — Compute a floating-point number to an integer power, possibly negative. Teaches fast exponentiation and the negative-exponent edge case.
Solution
Iterative repeated squaring: walk the bits of ; multiply the result by the current power of whenever the bit is 1. .
def my_pow(x: float, n: int) -> float:
if n < 0:
x, n = 1 / x, -n
result = 1.0
while n:
if n & 1: # this bit of n is set: multiply in the current power
result *= x
x *= x # x, x^2, x^4, x^8, ...
n >>= 1
return result
assert my_pow(3, 13) == 1594323
assert abs(my_pow(2.0, -2) - 0.25) < 1e-12
assert my_pow(5, 0) == 1
2. Majority Element (LeetCode 169) — An array has a value occurring more than half the time; find it. Teaches a divide-and-conquer combine step that needs a counting pass (the optimal answer is Boyer–Moore voting).
Solution
If is a majority of the whole, it is a majority of at least one half (otherwise it would occur at most times). So the answer is one of the two halves' majorities; count both in the current range. .
def majority_element(nums):
def solve(lo, hi): # majority of nums[lo:hi], which is guaranteed to exist
if hi - lo == 1:
return nums[lo]
mid = (lo + hi) // 2
left, right = solve(lo, mid), solve(mid, hi)
if left == right:
return left
# a majority of the whole is a majority of at least one half: count both candidates
cl = sum(1 for i in range(lo, hi) if nums[i] == left)
cr = sum(1 for i in range(lo, hi) if nums[i] == right)
return left if cl > cr else right
return solve(0, len(nums))
assert majority_element([2, 2, 1, 1, 1, 2, 2]) == 2
assert majority_element([3, 2, 3]) == 3
3. Maximum Subarray (LeetCode 53) — Largest sum of a non-empty contiguous run. Teaches the crossing case, and why Kadane wins.
Solution
Both versions from the lesson, checked against each other.
def max_subarray(nums):
def solve(lo, hi): # best sum of a non-empty subarray of nums[lo:hi]
if hi - lo == 1:
return nums[lo]
mid = (lo + hi) // 2
best = max(solve(lo, mid), solve(mid, hi))
s, best_left = 0, float("-inf") # best suffix of the left half
for i in range(mid - 1, lo - 1, -1):
s += nums[i]
best_left = max(best_left, s)
s, best_right = 0, float("-inf") # best prefix of the right half
for i in range(mid, hi):
s += nums[i]
best_right = max(best_right, s)
return max(best, best_left + best_right)
return solve(0, len(nums))
def kadane(nums):
best = cur = nums[0]
for v in nums[1:]:
cur = max(v, cur + v) # extend the run ending here, or start fresh
best = max(best, cur)
return best
assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray([-3, -1, -2]) == kadane([-3, -1, -2]) == -1
4. Sort an Array (LeetCode 912) — Sort without the library, in . Teaches writing merge sort with one buffer.
Hint
Strip the counting out of count_inversions above and you have it. Then try quicksort with a random pivot and three-way partitioning; the test data includes many duplicates.
5. Merge k Sorted Lists (LeetCode 23) — Combine sorted linked lists. Teaches divide and conquer over the lists rather than the elements.
Hint
Merge lists pairwise: merges, then , … Each round touches all nodes once and there are rounds: . A heap of size gives the same bound.
6. Kth Largest Element in an Array (LeetCode 215) — Find the -th largest without sorting. Teaches quickselect.
Hint
Partition around a random pivot, recurse into one side. Use three-way partitioning, because inputs with many equal values make two-way quickselect quadratic. Full code: Quickselect & Order Statistics.
7. Different Ways to Add Parentheses (LeetCode 241) — List every value an arithmetic expression can take under all parenthesisations. Teaches "split at every operator" and when memoization joins in.
Solution
The last operator applied splits the expression into a left and a right part; combine every left value with every right value. Substrings repeat, so cache them — the boundary between divide and conquer and DP.
from functools import lru_cache
def diff_ways_to_compute(expression: str):
@lru_cache(maxsize=None)
def ways(s: str):
out = []
for i, ch in enumerate(s):
if ch in "+-*": # split at every operator: it is the last one applied
for x in ways(s[:i]):
for y in ways(s[i + 1:]):
out.append(x + y if ch == "+" else x - y if ch == "-" else x * y)
return out or [int(s)] # no operator: s is a number
return ways(expression)
assert sorted(diff_ways_to_compute("2-1-1")) == [0, 2]
assert sorted(diff_ways_to_compute("2*3-4*5")) == [-34, -14, -10, -10, 10]
8. Search a 2D Matrix II (LeetCode 240) — Search a matrix whose rows and columns are sorted. Teaches when divide and conquer is not the best tool.
Hint
A quadrant-elimination divide and conquer works, but the staircase walk from the top-right corner (move left if too big, down if too small) is and simpler. Prove the staircase correct with an invariant.
9. Count of Smaller Numbers After Self (LeetCode 315) — For each element, count later elements smaller than it. Teaches per-element inversion counts.
Hint
Merge sort an array of indices by value. When a left element is output, add the number of right elements already output (they are smaller and came later) to that element's count. Or use a Fenwick tree over compressed values, scanning from the right.
10. Reverse Pairs (LeetCode 493) — Count pairs with . Teaches separating the counting pass from the merge pass when the condition is not the sort order.
Solution
With both halves sorted, for each left element advance a pointer through the right half while ; the pointer never moves back because the left half is increasing. Then merge. . (In Java or C++, compute in 64 bits.)
def reverse_pairs(nums):
a = list(nums)
def sort(lo, hi):
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
count = sort(lo, mid) + sort(mid, hi)
j = mid
for i in range(lo, mid): # both halves sorted: j only moves forward
while j < hi and a[i] > 2 * a[j]:
j += 1
count += j - mid
a[lo:hi] = sorted(a[lo:hi]) # a real merge is O(n); sorted() keeps the idea visible
return count
return sort(0, len(a))
assert reverse_pairs([1, 3, 2, 3, 1]) == 2
assert reverse_pairs([2, 4, 3, 5, 1]) == 3
11. Count of Range Sum (LeetCode 327) — Count subarrays whose sum lies in . Teaches turning a subarray question into a pair question on prefix sums, then counting cross pairs with two moving pointers.
Solution
A subarray has sum . Count pairs of prefix sums with : in the combine step, for each left the valid right form a window in the sorted right half, and both window ends only move forward.
def count_range_sum(nums, lower, upper):
pre = [0]
for v in nums:
pre.append(pre[-1] + v) # range sum (i, j] = pre[j] - pre[i]
def sort(lo, hi): # counts pairs i < j in pre[lo:hi] with lower <= pre[j]-pre[i] <= upper
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
count = sort(lo, mid) + sort(mid, hi)
a = b = mid
for i in range(lo, mid): # left half sorted; window [a, b) of right half moves forward
while a < hi and pre[a] - pre[i] < lower:
a += 1
while b < hi and pre[b] - pre[i] <= upper:
b += 1
count += b - a
pre[lo:hi] = sorted(pre[lo:hi])
return count
return sort(0, len(pre))
assert count_range_sum([-2, 5, -1], -2, 2) == 3
assert count_range_sum([0], 0, 0) == 1
12. Minimum Euclidean Distance (CSES 2194) — Closest pair among up to integer points; print the squared distance. Teaches the lesson's algorithm under real limits.
Hint
The closest_pair implementation above returns exactly what is asked. With coordinates in , a squared distance can reach , which fits in a signed 64-bit integer (max ≈ ) — just. In Python, read the input in one go with sys.stdin.buffer.read().split().
13. Median of Two Sorted Arrays (LeetCode 4) — Median of the union of two sorted arrays in . Teaches decrease and conquer on a partition point.
Hint
Binary search over how many elements the shorter array contributes to the left half of the union. A partition is correct when the largest left element on each side is at most the smallest right element on the other side. Work out the empty-side sentinels () on paper first.
14. Beautiful Array (LeetCode 932) — Build a permutation of with no such that . Teaches divide and conquer as construction.
Hint
If is beautiful, so are (all odd) and (all even), and odd-then-even concatenated is beautiful because odd + even is odd and never equals . Recurse on and .
Common mistakes & interview follow-ups
"What is the recurrence, and how do you solve it?" Always say it out loud: "two calls on half the input plus a linear merge, , Master theorem case 2, ." Interviewers check that you can derive the bound, not recite it.
"Why is Karatsuba faster if it still splits into halves?" Because the leaves dominate (), and the number of leaves is . Going from 4 to 3 recursive products changes the exponent from 2 to 1.585. The extra additions only affect the per-level cost, which does not dominate.
"Why only 7 points in the strip?" Give the packing argument: a rectangle, two squares, at most 4 points per square because each quarter holds at most one. Mention that the code stops on the -gap, not on a counter, so the bound is about running time only.
"Can you do closest pair faster?" Not in the algebraic decision-tree model: , by reduction from element distinctness. With hashing and floors, randomized expected (grid of cell size , rebuild when shrinks).
"Your maximum subarray is . Can you do ?" Kadane. Or return (total, best prefix, best suffix, best) from each call for an divide and conquer — and mention that this is the segment-tree node for range maximum-subarray queries.
"How deep does your recursion go?" for balanced splits. If the split can be unbalanced (quicksort), recurse on the smaller side and loop on the larger.
"Is this divide and conquer or DP?" If the subproblems are disjoint, divide and conquer. If the same subproblem can be reached twice, DP (memoize). "Different Ways to Add Parentheses" is the classic borderline case.
Mistakes interviewers watch for: < instead of <= in the inversion merge; 32-bit overflow in counts or squared distances; slicing arrays at every level; base cases that miss the empty or single-element input; two identical recursive calls in fast power.
Quick quiz
1. Solve and .
Answer
First: , , , : case 2, . Second: and is polynomially smaller: case 1, .
2. In the inversion trace, the final merge outputs 4 from the right half while [5, 8] are still waiting. Why does it add 2 and not look at 5 and 8 individually?
Answer
The left half is sorted, so every waiting element is at least as large as the next waiting one (5), which is already larger than 4. All waiting elements come before 4 in the original array. So each waiting element forms exactly one inversion with 4.
3. In the closest-pair trace, why are and never measured at the top level?
Answer
After –, . The -gap from to is 2, and , so the scan stops before computing the distance — they cannot be closer than 1.
4. How many single-digit multiplications does Karatsuba need for two 8-digit numbers, recursing to single digits? Schoolbook?
Answer
, so versus .
5. Why does the strip test use rather than ?
Answer
A point exactly from the line is at least from every point on the other side, so it cannot improve on . Strict inequality keeps the strip smaller; it does not affect correctness either way.
6. Write the recurrence for pow(x, n) = pow(x, n//2) * pow(x, n//2) (two calls). What is its running time?
Answer
: case 1 with , so — no better than the plain loop. Compute the half power once and square it.
Further reading / sources
- Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 4 (divide and conquer, Strassen, the Master theorem, Akra–Bazzi); §2.3 (merge sort); §33.4 (closest pair, the strip argument); Chapter 30 (FFT).
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005) — Chapter 5: counting inversions (§5.3), closest pair (§5.4), integer multiplication (§5.5), FFT (§5.6).
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — §2.2 (mergesort).
- Steven Skiena, The Algorithm Design Manual, 3rd ed. (2020) — Chapter 5 (divide and conquer, recurrences, FFT).
- A. Karatsuba and Yu. Ofman, "Multiplication of many-digital numbers by automatic computers", Doklady Akademii Nauk SSSR 145, 1962; and Karatsuba's own account, "The complexity of computations", Proceedings of the Steklov Institute of Mathematics 211, 1995.
- V. Strassen, "Gaussian elimination is not optimal", Numerische Mathematik 13, 1969.
- M. I. Shamos and D. Hoey, "Closest-point problems", 16th IEEE Symposium on Foundations of Computer Science, 1975.
- D. Harvey and J. van der Hoeven, "Integer multiplication in time ", Annals of Mathematics 193(2), 2021.
- J. Huang, T. M. Smith, G. M. Henry and R. A. van de Geijn, "Strassen's Algorithm Reloaded", SC16, 2016.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed. (2002) — Chapter 23 on fast matrix multiplication.
- cp-algorithms: Finding the nearest pair of points, Binary exponentiation.
- Jon Bentley, Programming Pearls, 2nd ed. (1999) — Column 8, the maximum subarray problem from cubic to linear.
Course navigation. Previous: Recursion & Backtracking. Next: Greedy Algorithms. Module overview: Algorithmic Paradigms. Course: DSA: Zero to Mastery.