Divide and Conquer: Mental Model with Merge Sort and Quick Sort

Divide and conquer is the algorithmic strategy of breaking a problem into smaller subproblems of the same shape, solving them recursively, and combining the results. The pattern shows up in sorting (merge sort, quick sort), searching (binary search), numerical algorithms (Karatsuba, FFT), and computational geometry (closest pair of points). Once you see the template, you can derive runtimes mechanically with the Master theorem.

The template

Every divide-and-conquer algorithm has three steps:

1. Divide the input into smaller pieces, usually of roughly equal size.
2. Conquer each piece by recursing.
3. Combine the partial results into a solution for the whole input.

def solve(problem):
    if is_small(problem):
        return solve_directly(problem)
    parts = divide(problem)
    answers = [solve(p) for p in parts]
    return combine(answers)

The art is choosing a split that makes the combine step cheap, or vice versa. Merge sort does the work in combine; quick sort does the work in divide. Both end up at O(n log n) average time, but for different reasons.

Merge sort

Split the array in half, sort each half recursively, then merge two sorted halves into one.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Properties worth memorizing:

• Time: O(n log n) in every case, best, average, and worst.
• Space: O(n) auxiliary because merging needs a buffer.
• Stable: equal elements keep their original order, which matters when sorting tuples by a secondary key.

Merge sort is the canonical example because the recurrence is simple: splitting is O(1) if you pass indices, sorting halves is 2T(n/2), and merging is O(n).

T(n) = 2T(n/2) + O(n)

Quick sort

Pick a pivot, partition the array so elements less than the pivot are left and greater are right, then recursively sort the two sides.

def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return
    p = partition(arr, lo, hi)
    quick_sort(arr, lo, p - 1)
    quick_sort(arr, p + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

Properties worth memorizing:

• Time: O(n log n) average, O(n^2) worst case (pathological pivots).
• Space: O(log n) recursion stack on average, O(n) in the worst case.
• In place: no auxiliary buffer needed.
• Not stable in this form.

The worst case happens when the pivot is consistently the minimum or maximum, for example on an already-sorted array with naive pivot choice. Production implementations defend against this with randomized pivots or median-of-three.

Recurrence relations

A recurrence describes the runtime in terms of subproblem runtimes. For divide and conquer, the form is almost always:

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

• a is the number of subproblems.
• n / b is the size of each subproblem.
• f(n) is the cost of the divide and combine steps at the current level.

Examples:

• Merge sort: T(n) = 2T(n/2) + O(n).
• Binary search: T(n) = T(n/2) + O(1).
• Karatsuba multiplication: T(n) = 3T(n/2) + O(n).
• Strassen matrix multiplication: T(n) = 7T(n/2) + O(n^2).

The Master theorem (informally)

Compare f(n) to n^(log_b a):

• If f(n) = O(n^(log_b a - eps)) for some eps > 0, then T(n) = O(n^(log_b a)). The subproblems dominate.
• If f(n) = O(n^(log_b a)), then T(n) = O(n^(log_b a) * log n). Subproblems and combine are balanced.
• If f(n) = O(n^(log_b a + eps)) and regularity holds, then T(n) = O(f(n)). The combine step dominates.

For merge sort, log_2 2 = 1 and f(n) = O(n) = O(n^1), so we are in case two and get O(n log n). For binary search, log_2 1 = 0 and f(n) = O(1) = O(n^0), again case two, giving O(log n). The theorem fails for non-polynomial f(n) like n log n; in those cases use the Akra-Bazzi method or analyze the recursion tree directly.

Problem 1: Maximum subarray (divide and conquer)

Given an integer array, return the maximum sum of any contiguous subarray.

The classic linear answer is Kadane’s algorithm, which belongs to Dynamic Programming Introduction. The divide-and-conquer version is also instructive: split the array, recurse on each half, and combine by computing the best subarray that crosses the midpoint.

def max_subarray(arr):
    def helper(lo, hi):
        if lo == hi:
            return arr[lo]
        mid = (lo + hi) // 2
        left = helper(lo, mid)
        right = helper(mid + 1, hi)

        # best subarray crossing the midpoint
        s, best_left = 0, float('-inf')
        for i in range(mid, lo - 1, -1):
            s += arr[i]
            best_left = max(best_left, s)
        s, best_right = 0, float('-inf')
        for j in range(mid + 1, hi + 1):
            s += arr[j]
            best_right = max(best_right, s)

        return max(left, right, best_left + best_right)

    return helper(0, len(arr) - 1)

Recurrence: T(n) = 2T(n/2) + O(n), so the total is O(n log n). Kadane beats this at O(n), but the divide-and-conquer version generalizes to 2D and to problems where Kadane does not apply.

Problem 2: Quickselect

Find the kth smallest element of an array in expected O(n) time.

Use the same partition routine as quick sort, but only recurse into the side that contains index k.

import random

def quickselect(arr, k):
    lo, hi = 0, len(arr) - 1
    while True:
        if lo == hi:
            return arr[lo]
        pivot_idx = random.randint(lo, hi)
        arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
        p = partition(arr, lo, hi)
        if p == k:
            return arr[p]
        elif p < k:
            lo = p + 1
        else:
            hi = p - 1

Each step shrinks the search range by a constant factor in expectation, giving T(n) = T(n/2) + O(n) and a total of O(n). The deterministic median-of-medians algorithm achieves O(n) worst case but with much larger constants.

When divide and conquer is the right tool

• The problem has natural structure where solutions on halves combine cleanly.
• Subproblems are independent (no overlap). If they overlap, switch to DP.
• The combine step is cheap relative to the size of the subproblems.

Searching a sorted array? Binary search. Sorting? Merge or quick. Counting inversions? Modified merge sort. Closest pair in 2D? Sort and recurse. The pattern keeps paying for itself.

Wrap up

Divide and conquer turns hard problems into “the same problem, but smaller” plus a combine step. Internalize the template, the merge sort recurrence, and the Master theorem rule of thumb, and you can analyze new algorithms in minutes. Pair it with Recursion Fundamentals for the implementation discipline and you will reach for it instinctively on the right problems.