12.1 Divide and Conquer

Prerequisites: Recursion and Merge Sort. This section illustrates the three-step process (divide, conquer, and combine) using the maximum subarray sum and inversion count problems. Neither of the two public functions modifies the input.

Merge Sort Leaves Some Questions

Divide-and-conquer typically follows three steps:

1. Divide: break a problem of size n into smaller subproblems;
2. Conquer: recursively solve each subproblem until reaching a base case that can be answered directly;
3. Combine: merge the subresults into a solution for the current problem.

Using recursion does not automatically imply divide-and-conquer. If subproblems overlap significantly, direct recursion recomputes the same states. Memoization or dynamic programming may let us reuse those results. Without a clear combination rule, splitting the problem won't magically yield a solution.

A Runnable Implementation

The maximum subarray function accepts an indexable sequence of integers. It raises ValueError for empty input and TypeError for non-integer elements. Integer addition gives the same exact sum regardless of grouping; floating-point rounding and NaN need a separate contract. The inversion counter copies an iterable before merging. Its elements must have a consistent ordering under <, excluding unordered values such as NaN; the function does not validate the entire comparison relation. Neither function modifies the input.

def max_subarray_sum(values):
    if not values:
        raise ValueError("max_subarray_sum requires a non-empty input")
    if any(not isinstance(value, int) for value in values):
        raise TypeError("values must contain integers")

    def solve(left, right):
        if left == right:
            return values[left]

        middle = (left + right) // 2
        best_left = solve(left, middle)
        best_right = solve(middle + 1, right)

        running = 0
        crossing_left = float("-inf")
        for index in range(middle, left - 1, -1):
            running += values[index]
            crossing_left = max(crossing_left, running)

        running = 0
        crossing_right = float("-inf")
        for index in range(middle + 1, right + 1):
            running += values[index]
            crossing_right = max(crossing_right, running)

        return max(best_left, best_right, crossing_left + crossing_right)

    return solve(0, len(values) - 1)

def count_inversions(values):
    working = list(values)
    buffer = [None] * len(working)

    def sort_and_count(left, right):
        if right - left <= 1:
            return 0

        middle = (left + right) // 2
        inversions = sort_and_count(left, middle)
        inversions += sort_and_count(middle, right)

        left_index = left
        right_index = middle
        output = left
        while left_index < middle and right_index < right:
            if not working[right_index] < working[left_index]:
                buffer[output] = working[left_index]
                left_index += 1
            else:
                buffer[output] = working[right_index]
                right_index += 1
                inversions += middle - left_index
            output += 1

        while left_index < middle:
            buffer[output] = working[left_index]
            left_index += 1
            output += 1
        while right_index < right:
            buffer[output] = working[right_index]
            right_index += 1
            output += 1

        working[left:right] = buffer[left:right]
        return inversions

    return sort_and_count(0, len(working))

if __name__ == "__main__":
    values = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    assert max_subarray_sum(values) == 6
    assert max_subarray_sum([-5]) == -5
    assert max_subarray_sum([-8, -3, -6]) == -3

    sample = [2, 4, 1, 3, 5]
    assert count_inversions(sample) == 3
    assert sample == [2, 4, 1, 3, 5]
    assert count_inversions([]) == 0
    assert count_inversions([2, 2, 1]) == 2

    print("Divide and conquer check passed")

Maximum Subarray: Filling in the Cross-Midpoint Candidates

The maximum sum contiguous subarray can only occupy three positions:

• Entirely in the left half;
• Entirely in the right half;
• Spanning across the midpoint.

The first two cases are handled by recursive calls. The cross-midpoint subarray must include middle and middle+1, so we compute the maximum suffix sum extending left from the midpoint, and the maximum prefix sum extending right from the midpoint, then add those two values together.

The recursive subproblems on the left and right halves do not overlap; the cross-midpoint candidate is part of the merging step. At each level of recursion, the merging step scans O(n) elements, leading to the recurrence:

T(n) = 2T(n/2) + Theta(n) = Theta(n log n)

This implementation returns one sum, uses O(log n) recursive stack space, and does not copy subarrays at each level. These bounds count integer addition and comparison as constant-time operations; arbitrary-size integers also incur costs based on bit length. The recurrence abbreviates both halves as n/2; rounding their sizes up and down does not change the bound.

Kadane's algorithm provides a Θ(n) alternative. We study divide-and-conquer here not because it is the fastest, but to practice the principle: "when the subproblem answers are insufficient, what kind of candidate is missing in the merge step?"

Inversion Count: Counting During Sorting

An inversion pair is a pair of elements with indices i < j and values[i] > values[j]. After both halves are sorted, if the current value on the right is less than the current value on the left, then all remaining values from left_index to middle-1 on the left half are larger:

New inversion count = middle - left_index

Equal values do not form an inversion. The condition not right < left takes from the left unless the right value is smaller, requiring only <. Each element is processed once per merge level: for n ≥ 2, time is Θ(n log n), auxiliary space is O(n), and the recursive stack is O(log n). Slice assignment creates temporary slices but keeps peak space at O(n). Empty and singleton inputs both return 0. Princeton’s inversion counter uses the same definition.

Python integers won't overflow due to large counting; when processing large arrays in fixed-width languages, ensure the maximum inversion count n(n-1)/2 does not exceed the integer type.

Divide and Conquer, Backtracking, and Dynamic Programming

Method	Subproblem Relationship	What Happens at Current Level	Typical Risks
Divide and conquer	Typically independent	Combine subproblem results	High cost of combination
Backtracking	Enumerates branches of choice tree	Make a choice, recurse, undo	State not restored or combinatorial explosion
Dynamic Programming	States heavily overlap	Cache and reuse subproblem results	Missing state definition or transition logic

Boundaries are not determined by syntax. The same problem can be solved with multiple algorithms; the deciding factor is the structure of subproblems, the output requirements, and complexity, not whether recursion appears in the function.

Check the Merge Steps

1. Manually compute the three-level merge of [2, 4, 1, 3, 5] and identify the inversions introduced at each step.
2. Implement an O(n²) brute-force solution to serve as a test oracle for random short arrays.
3. Modify the maximum subarray function to return both start and end indices; what tie-breaking rule should be used when the maximum sums are equal?
4. Explain why a fully negative array cannot use zero as the initial cross-value.
5. Compare Kadane’s algorithm with the divide-and-conquer version: what intermediate information does each maintain?

The Merge Rule Determines the Algorithm

The hallmark of divide-and-conquer isn't that the code is recursive; it's whether the subproblems can be solved independently and whether the current level can synthesize a solution at controlled cost. In the maximum subarray problem, the merge phase supplements cross-boundary candidates; in the inversion count, ordered merging enables bulk counting. Both transform originally quadratic enumeration into a product of recursion depth and per-level work.

The next lesson explores a different recursive tree: backtracking doesn't combine two independent solutions, but instead makes decisions on a choice tree, checks constraints, and undoes state as needed.