Home / Algorithms

Divide and Conquer

Algorithms & Data StructuresBy Ashish JangraUpdated 15 September 2026

Split the problem, solve the pieces, combine the answers. It is the paradigm behind merge sort, quick sort and binary search — and the recursion tree shows exactly where the log n comes from.

Controls

Algorithm

array size n8

The Recursion Tree

step 0

Insight

Three phases at every level: divide into subproblems, conquer them recursively, combine the results.

T(n) = a·T(n/b) + f(n) ↑ ↑ ↑ pieces size combine

levels0

work / level0

total0

Complexity

Merge sort O(n log n)

Binary search O(log n)

Depth O(log n)

Divide and Conquer

Break it up, solve the pieces, stitch them back — and the log n falls out of the tree depth.

The problem it solves

Divide and conquer solves a problem by splitting it into smaller instances of itself, solving those recursively, and combining the results. Three phases: divide, conquer, combine.

Where log n Comes From

The recursion tree makes it obvious. Each level halves the problem size, so it takes log₂n levels to reach size 1 — that is the height of the tree.

In merge sort, every level does O(n) total work (each element is touched once during merging), and there are log n levels. Multiply: O(n log n). Raise n in the lab and watch the level count grow by exactly one each time you double.

The Master Theorem

For recurrences of the form T(n) = a·T(n/b) + f(n) — a subproblems of size n/b, plus f(n) to combine — the answer depends on which dominates:

Leaves dominate — most work at the bottom.
Balanced — equal work per level, giving the extra log factor. Merge sort sits here: T(n) = 2T(n/2) + O(n) → O(n log n).
Root dominates — the combine step is the expensive part.

Binary search is T(n) = T(n/2) + O(1): one subproblem, trivial combine — so O(log n) total. It discards half the work rather than recursing into both halves, which is why it beats merge sort's complexity.

The Combine Step Is Where the Work Lives

Dividing is usually trivial — compute a midpoint. The interesting engineering is almost always in combining.

Merge sort — merging two sorted halves is O(n) and needs O(n) scratch space.
Quick sort — inverts the pattern: it partitions before recursing, so the combine step is free. That is why it sorts in place.
Maximum subarray — the answer may straddle the midpoint, so combining must scan outward from the centre.

Why It Matters Beyond Sorting

Divide and conquer parallelises naturally — independent subproblems can run on different cores, which is why it underpins MapReduce and most parallel frameworks. It is also the pattern behind Karatsuba multiplication, the Fast Fourier Transform, and closest-pair-of-points.

Split, solve, combine

Divide and conquer solves a problem by breaking it into independent subproblems of the same kind, solving those recursively, and combining the results.

Three steps, and the third is where the algorithms differ:

Divide the problem into smaller instances. Conquer each recursively, until a base case is trivial. Combine the sub-results into the answer.

Algorithm	Divide	Combine
Merge sort	Split in half	Merge two sorted halves — O(n)
Quick sort	Partition around a pivot	Nothing — work done in the divide
Binary search	Halve the range	Nothing — one side is discarded
Karatsuba multiplication	Split the digits	Three products and some additions
Strassen's matrix product	Split into quadrants	Seven products and additions
Closest pair of points	Split by x-coordinate	Check the strip near the boundary

Note that quick sort and merge sort are mirror images: quick sort does its work partitioning before recursing, merge sort does it merging afterwards. Binary search is the degenerate case where one subproblem is discarded entirely, which is why it is O(log n) rather than O(n log n).

The master theorem, informally

For a recurrence of the form

T(n) = a · T(n/b) + f(n)

— a subproblems, each of size n/b, plus f(n) work to divide and combine — the complexity depends on which term dominates.

Case	Condition	Result
Combine dominates	f(n) grows faster than n^(log_b a)	O(f(n))
Balanced	f(n) ≈ n^(log_b a)	O(f(n) log n)
Recursion dominates	f(n) grows slower	O(n^(log_b a))

Applied to merge sort: two subproblems of half the size plus O(n) merging — a = 2, b = 2, so n^(log₂2) = n, which matches f(n) = n. Balanced case, giving O(n log n).

Applied to binary search: one subproblem of half the size plus O(1) — a = 1, b = 2, so n^(log₂1) = n⁰ = 1, matching f(n) = 1. Balanced case, giving O(log n).

The useful intuition without the algebra: count the levels of recursion (log_b n) and the work per level. If the work per level is constant in total, the answer is that work times the number of levels.

Divide and conquer against dynamic programming

The distinction is one word: independence.

Divide and conquer applies when subproblems do not overlap. Merge sort's two halves share nothing, so each is solved once and there is nothing to cache.

Dynamic programming applies when they do overlap. Fibonacci's fib(n-1) and fib(n-2) share almost everything, so solving each independently is exponentially wasteful and memoisation is essential.

	Divide and conquer	Dynamic programming
Subproblems	Independent	Overlapping
Caching	Pointless	Essential
Typical direction	Top-down recursion	Either
Examples	Merge sort, binary search	Fibonacci, edit distance, knapsack

Recursive Fibonacci written as divide and conquer is O(2ⁿ) precisely because the subproblems overlap and nothing is cached. Adding @lru_cache converts it to dynamic programming and O(n). Recognising which situation you are in decides whether caching is the fix.

Where the log comes from, and which step decides the total

Divide and conquer splits a problem, solves the pieces and combines them. The complexity is decided almost entirely by the combine step, and the Master Theorem is a way of reading that off. It is easier to believe after counting the work at each level of an actual recursion.

example_01.pyPython

def merge_sort(a, level=0, work=None):
    work = {} if work is None else work
    work[level] = work.get(level, 0) + len(a)
    if len(a) <= 1:
        return a, work
    mid = len(a) // 2
    left, _ = merge_sort(a[:mid], level + 1, work)
    right, _ = merge_sort(a[mid:], level + 1, work)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:], work


import random
n = 64
_, work = merge_sort(random.Random(3).sample(range(n), n))
print("merge sort on %d elements" % n)
print("%7s %12s %16s" % ("level", "subproblems", "elements seen"))
total = 0
for lvl in sorted(work):
    count = 2 ** lvl
    total += work[lvl]
    print("%7d %12d %16d" % (lvl, count, work[lvl]))
print("%7s %12s %16d" % ("", "total", total))

# Every level touches all n elements, and there are log2(n) + 1 levels.
# n per level times log n levels is where n log n comes from -- not from
# the recursion itself, but from the combine step being linear.
#
# Change what the combine step costs and the total changes with it. The
# Master Theorem for T(n) = a*T(n/b) + f(n) says the answer is decided by
# whether f(n) is smaller, equal, or larger than n^(log_b a):

import math
print()
print("%-34s %-14s %-16s %s" % ("algorithm", "a, b", "combine f(n)", "total"))
rows = [
    ("binary search",           1, 2, "O(1)",     "O(log n)"),
    ("merge sort",              2, 2, "O(n)",     "O(n log n)"),
    ("naive matrix multiply",   8, 2, "O(n^2)",   "O(n^3)"),
    ("Strassen",                7, 2, "O(n^2)",   "O(n^2.81)"),
]
for name, a, b, f, total_s in rows:
    crit = math.log(a, b)
    print("%-34s a=%d b=%d       %-16s %s   (n^%.2f)" % (
        name, a, b, f, total_s, crit))

# Read the last column. Strassen is famous for one reason visible right
# there: it does SEVEN multiplications instead of eight on the same split,
# and that single change to `a` moves the exponent from 3 to 2.81. The
# combine step got messier and the total still improved, because the
# exponent is set by how many subproblems you make, not by how tidy the
# combining is.
#
# And binary search is the degenerate case worth noticing: it makes ONE
# subproblem, not two. Half the input is discarded rather than solved, so
# there is no combine step at all -- which is why it is log n and not n.

def bsearch(a, target, depth=0):
    if not a:
        return depth
    mid = len(a) // 2
    if a[mid] == target:
        return depth + 1
    if a[mid] < target:
        return bsearch(a[mid + 1:], target, depth + 1)
    return bsearch(a[:mid], target, depth + 1)


data = list(range(1000))
print()
print("binary search recursion depth on 1000 items:",
      bsearch(data, 777), "  log2(1000) = %.1f" % math.log2(1000))

# One branch taken, one discarded, at every level. When both branches must
# be solved you get n log n or worse; when one can be thrown away you get
# log n. That distinction, not the splitting, is what the technique is
# really about.

Output

Experiments to try

Step through merge sort at n = 8. Watch the tree split down to single elements, then merge back upward.
Count the levels: 3 for n = 8. That is log₂8, and it is exactly where the log n factor comes from.
Double n to 16. The level count rises by one, not by double — logarithmic growth, visible.
Switch to binary search. Only one branch is followed at each level, so the tree is a path — O(log n) rather than O(n log n).
Compare work per level. Merge sort does O(n) at every level; binary search does O(1). That single difference produces the whole complexity gap.

Where that leaves you

Divide and conquer gets its log factor from tree depth: halving repeatedly takes log n levels. Multiply that by the work per level and you have the complexity. Recursing into every branch gives O(n log n); discarding all but one gives O(log n).

Why it parallelises well

Independent subproblems can be solved simultaneously, which is the structural reason divide and conquer maps well onto multiple cores.

Merge sort's two halves can be sorted concurrently; only the merge must wait. Quick sort's two partitions likewise. That is why parallel sorting libraries are built on these algorithms rather than on insertion or bubble sort.

The practical pattern is a threshold: recurse in parallel while the subproblem is large, and switch to sequential below a size where thread overhead dominates.

from concurrent.futures import ThreadPoolExecutor

def parallel_merge_sort(arr, threshold=10_000, pool=None):
    if len(arr) <= 1:
        return arr
    if len(arr) < threshold:
        return sorted(arr)                     # sequential below the threshold
    mid = len(arr) // 2
    with ThreadPoolExecutor(2) as ex:
        left = ex.submit(parallel_merge_sort, arr[:mid], threshold)
        right = ex.submit(parallel_merge_sort, arr[mid:], threshold)
    return merge(left.result(), right.result())

In Python the GIL limits the benefit for pure-Python work, so this pattern matters more with multiprocessing, or in languages without a global lock. The structure is the point: the recursion tree is a natural task graph.

The same shape underlies MapReduce — divide the data, process independently, combine — which is divide and conquer across machines rather than cores.

Algorithms worth knowing beyond sorting

Karatsuba multiplication. Multiplying two n-digit numbers naively takes O(n²) digit products. Karatsuba splits each number in half and observes that three products suffice rather than four, giving O(n^1.585). Python's integers use it above a threshold, which is why multiplying very large integers is faster than the schoolbook method would suggest.

Strassen's algorithm. The same trick for matrices: seven multiplications of quadrants instead of eight, giving O(n^2.807) instead of O(n³). Rarely used in practice because of numerical stability and constant factors, and it proved that the obvious bound was not the limit.

Closest pair of points. Sort by x, split, recurse, then check only the narrow strip near the dividing line. O(n log n) rather than the obvious O(n²).

Fast Fourier transform. Divide and conquer on the frequency domain, O(n log n) instead of O(n²) — and arguably the most consequential algorithm in the list, underlying signal processing, audio and image compression, and fast polynomial multiplication.

Common mistakes

Using it where subproblems overlap. That is dynamic programming, and without caching the cost is exponential.
Forgetting the base case, giving infinite recursion.
An expensive combine step that dominates and negates the saving.
Recursion depth on large inputs in Python — convert to iteration or raise the limit.
Ignoring the constant factor. Recursion has overhead; below a threshold a simple loop wins, which is why real sorts switch to insertion sort for small subarrays.
Copying data at every level. arr[:mid] allocates; passing indices into one array avoids it.

Questions people ask

How is this different from plain recursion? Divide and conquer specifically splits into several independent subproblems and combines their results. Simple recursion may reduce the problem by one step.

When should I use dynamic programming instead? When subproblems overlap, so caching pays.

Does it always give O(n log n)? No — it depends on how many subproblems, how much smaller they are, and the combine cost. The master theorem gives the answer.

Why do real sorts switch to insertion sort? Recursion overhead exceeds the asymptotic benefit below roughly 32 elements.

Is binary search divide and conquer? Yes, in the degenerate form where one subproblem is discarded rather than solved.

Does it parallelise? Naturally, because the subproblems are independent — which is what makes it the basis for parallel sorting and MapReduce.

Recap in one screen

Divide into independent subproblems, solve recursively, combine the results.
The master theorem gives the complexity from the number of subproblems, their size, and the combine cost.
Independence is what distinguishes it from dynamic programming, where overlap makes caching essential.
Independent subproblems parallelise naturally, which is why parallel sorts and MapReduce have this shape.
Watch the constant factor: real implementations switch to a simple loop below a size threshold.

Where the parallel version actually helps

Divide and conquer looks like it should parallelise for free, and in Python it does not — the interpreter lock means threads cannot run bytecode simultaneously, so a recursive split across threads gains nothing. Two pages work through what does:

The GIL, and what it actually locks — why threads overlap waiting and never overlap computing, measured.
Threads or processes: what is and is not shared — processes do run in parallel, and the cost is the pickle boundary each subproblem has to cross.
Pools and futures with concurrent.futures — the same split, expressed as submit per subproblem and a Future per result, which is closer to how you would actually write it than raw threads.

Run it in Python

Two problems that look nothing alike solved by the same shape: fast exponentiation, which turns 1,000 multiplications into 10, and counting inversions during a merge, which does in n log n what the obvious loop does in n².

divide_and_conquer.pyPython 3

# Divide and conquer: split, solve the pieces, combine.

# --- 1. exponentiation by squaring -------------------------------------
def power(base, exp, depth=0):
    pad = "  " * depth
    if exp == 0:
        return 1
    half = power(base, exp // 2, depth + 1)      # ONE recursive call, not two
    result = half * half
    if exp % 2:
        result *= base                           # odd: one extra factor
    print(f"{pad}power({base}, {exp}) = {result}")
    return result


print("2 ** 10 by squaring:")
print("result:", power(2, 10))
print("multiplications: about log2(10) = 4, not 10")

# --- 2. counting inversions while merge sorting ------------------------
def sort_and_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, x = sort_and_count(a[:mid])
    right, y = sort_and_count(a[mid:])

    merged, z = [], 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            # left[i:] are ALL bigger than right[j], so they are all inversions
            z += len(left) - i
            merged.append(right[j]); j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, x + y + z


def count_brute(a):
    return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])


data = [2, 4, 1, 3, 5, 8, 7, 6]
sorted_data, inversions = sort_and_count(data)
print()
print("list       :", data)
print("sorted     :", sorted_data)
print("inversions :", inversions, "(brute force agrees:", count_brute(data), ")")
print()
print("Brute force compares every pair: O(n^2).")
print("The merge counts them in blocks while it is sorting anyway: O(n log n).")

Output

How the code works

half = power(base, exp // 2, depth + 1)One recursive call, and its result is used twice. Writing power(b, n//2) * power(b, n//2) instead looks identical and is exponentially slower — the saving is in reusing the value, not in the halving.
if exp % 2: result *= baseHandles the odd case, where halving loses a factor. This is where off-by-one errors live in every implementation of this function.
left, x = sort_and_count(a[:mid])The divide step. Each half is solved independently, and the returned count is the number of inversions within that half.
z += len(left) - iThe combine step, and the clever line. When an item from the right half wins, every remaining item on the left is greater than it, so they are all inversions — counted in one addition instead of one by one.
x + y + zLeft, right, and across. Every inversion is in exactly one of those three categories, which is the proof that the count is complete. That decomposition is the divide-and-conquer pattern in general.

Change one thing

Compute power(2, 1000). Ten recursive calls, and Python's unbounded integers print the whole 302-digit result.
Run the inversion counter on a reversed list of 12 items. The answer is n(n−1)/2, the maximum possible — and it is the same number insertion sort would charge you in shifts.
Time both counters on a list of 2,000 random numbers. The brute force does two million comparisons; the merge does about twenty thousand.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

Why does exponentiation by squaring make ONE recursive call and reuse the result?
Counting inversions during a merge is O(n log n) because, when an item from the right half wins:
Divide and conquer proves its answer complete by showing every case falls into:

Cheat sheet

Divide and Conquer

Split the problem, solve the pieces, combine the answers. It is the paradigm behind merge sort, quick sort and binary search — and the recursion tree shows exactly where the log n comes from.

ALGORITHMS · vizlearn.in/dsa/divide_and_conquer.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

About VizLearn GitHub LinkedIn Contact

Divide and Conquer

Controls

The Recursion Tree

Insight

Complexity

Divide and Conquer

The problem it solves

Where log n Comes From

The Master Theorem

The Combine Step Is Where the Work Lives

Why It Matters Beyond Sorting

Split, solve, combine

The master theorem, informally

Divide and conquer against dynamic programming

Where the log comes from, and which step decides the total

Experiments to try

Where that leaves you

Why it parallelises well

Algorithms worth knowing beyond sorting

Common mistakes

Questions people ask

Recap in one screen

Where the parallel version actually helps

Run it in Python

How the code works

Change one thing

Where this runs

Check yourself

Divide and Conquer

More in Algorithms

About the author