Data Structures & AlgorithmsDivide and Conquer

What Is Divide and Conquer?

LevelIntermediate

Duration60 mins

TopicDivide and Conquer

4 / 4

Combining Solutions

The Final Assembly

After dividing a problem and conquering its subproblems, we arrive at the final phase: COMBINE. This is where the individual solutions are assembled into a solution for the original problem. The combine step is often where the algorithm's elegance—or complexity—becomes most apparent.

The combine phase varies dramatically across D&C algorithms:

In binary search, combination is trivial: just return the result from the single explored subproblem
In quicksort, combination is implicit: partitioned elements are already in correct relative positions
In merge sort, combination is the heavy lift: merging two sorted arrays requires O(n) careful work
In Strassen's matrix multiplication, combination involves adding and subtracting submatrices in a specific pattern

Understanding these different combine strategies illuminates why D&C algorithms have different complexities and trade-offs. The cost of the combine step, multiplied by the number of levels, determines the overall runtime.

What You Will Learn

By the end of this page, you will understand different combination strategies used in D&C algorithms, analyze how combine complexity affects overall runtime, and design combine steps that efficiently integrate subproblem solutions.

The Role of the Combine Step

The combine step serves a critical function: it synthesizes partial solutions into a complete solution. Without correct combination, even perfectly solved subproblems yield wrong answers.

What Combination Must Achieve:

Correctness: The combined solution must correctly solve the original problem, given correct subproblem solutions
Completeness: No information from subproblem solutions should be lost or misrepresented
Efficiency: The combine step should not dominate the algorithm's complexity unnecessarily

The Combine Step in the Big Picture:

Recall the D&C recurrence:

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

Here, f(n) represents the combined cost of the divide and combine steps. In many algorithms:

Divide is O(1) or O(n)
Combine is O(1) to O(n²) depending on the algorithm

The relative cost of f(n) compared to the recursive work (a·T(n/b)) determines the overall complexity via the Master Theorem:

If f(n) is small: recursion dominates
If f(n) is large: combine/divide dominates
If balanced: all levels contribute equally

Combine Complexity in Classic D&C Algorithms
Algorithm	Divide Cost	Combine Cost	Overall Complexity
Binary Search	O(1)	O(1)	O(log n)
Merge Sort	O(1)	O(n) merge	O(n log n)
Quicksort	O(n) partition	O(1)	O(n log n) average
Maximum Subarray (D&C)	O(1)	O(n) cross-boundary	O(n log n)
Karatsuba Multiplication	O(n)	O(n) additions	O(n^1.585)
Strassen's Matrix Mult	O(n²)	O(n²) additions	O(n^2.807)

Where Does the Work Happen?

Different algorithms distribute work differently: Merge sort puts all sorting 'work' in the combine step (merging). Quicksort puts all sorting 'work' in the divide step (partitioning). Understanding this helps you optimize the right part of the algorithm.

Common Combination Patterns

Most combine steps fall into recognizable patterns. Learning these patterns helps you design combine steps for novel problems.

Pattern 1: Trivial Combination (O(1))

The simplest case: subproblem solutions are already the full solution, or require minimal work to assemble.

Examples:

Binary search: Return the index found in a subproblem
Quicksort: Partitioned array is already in order (implicit combination)
Finding maximum: Return max of two subproblem maxima

# Maximum via D&C: O(1) combine
def max_dnc(arr, left, right):
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_max = max_dnc(arr, left, mid)
    right_max = max_dnc(arr, mid + 1, right)
    return max(left_max, right_max)  # O(1) combination!

Pattern 2: Aggregation (O(1) or O(k) where k is small)

Combine by applying an associative operation (sum, product, min, max, count, etc.).

Examples:

Sum array: Add subproblem sums
Count inversions: Add subproblem counts plus cross-boundary count
Tree size: Sum of subtree sizes plus one

# Sum via D&C: O(1) combine
def sum_dnc(arr, left, right):
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_sum = sum_dnc(arr, left, mid)
    right_sum = sum_dnc(arr, mid + 1, right)
    return left_sum + right_sum  # O(1) aggregation

Pattern 3: Merge (O(n))

Combine by interleaving or merging subproblem solutions based on their elements.

Examples:

Merge sort: Merge two sorted arrays into one
Maximum crossing subarray: Scan from midpoint in both directions
Closest pair: Check cross-boundary pairs

This pattern involves examining every element at each level, contributing O(n) work per level and O(n log n) total.

Merge Pattern: O(n) Combine
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def merge(left: list[int], right: list[int]) -> list[int]:
    """
    Classic O(n) merge operation.
    
    Combines two sorted lists by comparing heads and advancing.
    Total comparisons: at most len(left) + len(right) - 1
    """
    result = []
    i = j = 0
    
    # Compare and advance until one list is exhausted
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Append remaining elements (no comparisons needed)
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result
 
 
# Analysis:
# - Each element is appended exactly once: O(n)
# - Each comparison advances at least one pointer: at most n-1 comparisons
# - Total: O(n) time, O(n) auxiliary space

Pattern 4: Complex Recombination (O(n²) or specialized)

Some algorithms require sophisticated combination logic:

Examples:

Strassen's algorithm: Add/subtract specific submatrices
FFT: Combine using roots of unity
Convex hull: Merge hulls along tangent lines

These patterns often arise in algorithms that achieve subquadratic complexity for traditionally quadratic problems.

The Merge Operation: A Deep Dive

The merge operation is the most common non-trivial combine pattern. Understanding it deeply pays dividends across many D&C algorithms.

The Merge Invariant:

At each step of merging two sorted arrays A and B into result R:

All elements added to R are in sorted order
The next smallest unprocessed element is at A[i] or B[j]
Choosing min(A[i], B[j]) maintains sortedness

Why Merge is O(n):

Each comparison either:

Adds an element from A to R (advances i), or
Adds an element from B to R (advances j)

Total elements added: |A| + |B| = n Total comparisons: at most n - 1 (when arrays interleave perfectly)

Space-Time Tradeoff in Merge:

Standard merge uses O(n) auxiliary space. In-place merging is possible but complex:

Simple in-place approaches are O(n²)
Sophisticated in-place merge (block merging) is O(n) but with huge constants
In practice, O(n) auxiliary space is almost always preferred

Merge Sort with Detailed Combine Phase
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def merge_sort_detailed(arr: list[int]) -> list[int]:
    """
    Merge sort with detailed combine phase analysis.
    """
    
    def merge_sort_helper(arr: list[int], depth: int) -> list[int]:
        # Track work at each level
        indent = "  " * depth
        
        # Base case
        if len(arr) <= 1:
            return arr[:]
        
        # Divide
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        # Conquer
        sorted_left = merge_sort_helper(left, depth + 1)
        sorted_right = merge_sort_helper(right, depth + 1)
        
        # Combine (merge)
        result = []
        i = j = 0
        comparisons = 0
        
        while i < len(sorted_left) and j < len(sorted_right):
            comparisons += 1
            if sorted_left[i] <= sorted_right[j]:
                result.append(sorted_left[i])
                i += 1
            else:
                result.append(sorted_right[j])
                j += 1
        
        result.extend(sorted_left[i:])
        result.extend(sorted_right[j:])
        
        print(f"{indent}Merged {sorted_left} + {sorted_right}")
        print(f"{indent}  → {result} ({comparisons} comparisons)")
        
        return result
    
    return merge_sort_helper(arr, 0)
 
 
# Run with analysis
print("Merge Sort Combine Phase Analysis")
print("=" * 50)
result = merge_sort_detailed([38, 27, 43, 3, 9, 82, 10])
print(f"
Final result: {result}")

Output demonstration:

Merge Sort Combine Phase Analysis
==================================================
      Merged [38] + [27]
        → [27, 38] (1 comparisons)
      Merged [43] + [3]
        → [3, 43] (1 comparisons)
    Merged [27, 38] + [3, 43]
      → [3, 27, 38, 43] (3 comparisons)
      Merged [9] + [82]
        → [9, 82] (1 comparisons)
      Merged [9, 82] + [10]
        → [9, 10, 82] (2 comparisons)
  Merged [3, 27, 38, 43] + [9, 10, 82]
    → [3, 9, 10, 27, 38, 43, 82] (6 comparisons)

Final result: [3, 9, 10, 27, 38, 43, 82]

Notice how:

Deepest merges happen first (bottom-up in the recursion tree)
Comparison count scales with merge size
Total work per level sums to O(n)

Stability Through Merge

Merge sort's stability (equal elements maintain relative order) comes from the merge step. By using ≤ instead of < when comparing elements, equal elements from the left array come before equal elements from the right, preserving the original order within equal groups.

Handling Cross-Boundary Cases

Many D&C algorithms have solutions that span the boundary between subproblems. These cross-boundary cases require explicit handling in the combine step.

The Cross-Boundary Problem:

When dividing a problem at a midpoint, some solutions might:

Start in the left subproblem and end in the right subproblem
Depend on elements from both sides simultaneously
Not be captured by either subproblem alone

Example: Maximum Subarray Sum

Consider finding the maximum sum contiguous subarray:

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Midpoint: after index 3 (after value 4)

The answer is [4, -1, 2, 1] with sum 6.
This subarray SPANS the midpoint!

Left subproblem thinks max is [1] = 1
Right subproblem thinks max is [4] = 4
Neither alone finds the cross-boundary answer of 6

Solution Strategy:

Explicitly find the best cross-boundary solution during the combine step:

Find best suffix of left subproblem (ending at midpoint)
Find best prefix of right subproblem (starting just after midpoint)
Combine them (they share the boundary, so concatenation is valid)
Compare cross-boundary result with subproblem results

Maximum Subarray with Cross-Boundary Handling
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def max_subarray(arr: list[int], left: int, right: int) -> tuple[int, int, int]:
    """
    Find maximum subarray using D&C with cross-boundary handling.
    
    Returns: (max_sum, start_index, end_index)
    """
    # Base case: single element
    if left == right:
        return (arr[left], left, left)
    
    mid = (left + right) // 2
    
    # CONQUER: Find max subarray in each half
    left_max, left_start, left_end = max_subarray(arr, left, mid)
    right_max, right_start, right_end = max_subarray(arr, mid + 1, right)
    
    # COMBINE: Find max crossing subarray
    cross_sum, cross_start, cross_end = max_crossing(arr, left, mid, right)
    
    # Return the best of three candidates
    if left_max >= right_max and left_max >= cross_sum:
        return (left_max, left_start, left_end)
    elif right_max >= left_max and right_max >= cross_sum:
        return (right_max, right_start, right_end)
    else:
        return (cross_sum, cross_start, cross_end)
 
 
def max_crossing(arr: list[int], left: int, mid: int, right: int) -> tuple[int, int, int]:
    """
    Find maximum subarray that must cross the midpoint.
    
    Key insight: Such a subarray is the concatenation of:
    - Best suffix of left half (ending at mid)
    - Best prefix of right half (starting at mid+1)
    """
    # Find best suffix of left half
    left_sum = float('-inf')
    current = 0
    max_left_idx = mid
    for i in range(mid, left - 1, -1):  # Go from mid backwards
        current += arr[i]
        if current > left_sum:
            left_sum = current
            max_left_idx = i
    
    # Find best prefix of right half
    right_sum = float('-inf')
    current = 0
    max_right_idx = mid + 1
    for i in range(mid + 1, right + 1):  # Go from mid+1 forwards
        current += arr[i]
        if current > right_sum:
            right_sum = current
            max_right_idx = i
    
    return (left_sum + right_sum, max_left_idx, max_right_idx)
 
 
# Test
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, start, end = max_subarray(arr, 0, len(arr) - 1)
print(f"Maximum sum: {max_sum}")
print(f"Subarray: {arr[start:end+1]} (indices {start} to {end})")
# Output:
# Maximum sum: 6
# Subarray: [4, -1, 2, 1] (indices 3 to 6)

Cross-Boundary in Other Algorithms:

Closest pair of points: After finding closest pairs within each half, must check pairs crossing the dividing line. Uses clever observation that only O(n) pairs need checking.
Counting inversions: Inversions within each half are counted recursively. Cross-boundary inversions are counted during merge: each time we pick from the right array, we count how many left-array elements remain.
Convex hull (merge): Individual hulls are found recursively. Merging requires finding upper and lower tangent lines between hulls.

Don't Forget Cross-Boundary Cases

A common D&C bug is correctly solving subproblems but forgetting cross-boundary contributions in the combine step. Always ask: 'Can the optimal solution span the division point?' If yes, your combine step must explicitly handle it.

Combine Complexity and the Master Theorem

The combine step's complexity directly impacts the overall D&C algorithm complexity. Understanding this relationship requires the Master Theorem.

The D&C Recurrence:

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

Where:

a = number of subproblems (typically 2 in binary D&C)
b = factor by which input shrinks (typically 2 for halving)
f(n) = cost of divide + combine (often dominated by combine)

Master Theorem Cases (simplified):

Let c = log_b(a) (the critical exponent)

If f(n) = O(n^(c-ε)): Recursion dominates → T(n) = Θ(n^c)
If f(n) = Θ(n^c · log^k n): Balanced → T(n) = Θ(n^c · log^(k+1) n)
If f(n) = Ω(n^(c+ε)): Combine dominates → T(n) = Θ(f(n))

Master Theorem Applied to Common D&C
Algorithm	Recurrence	a, b	f(n)	Case	Result
Binary Search	T(n) = T(n/2) + O(1)	1, 2	O(1)	Case 2 (k=0)	O(log n)
Merge Sort	T(n) = 2T(n/2) + O(n)	2, 2	O(n)	Case 2 (k=0)	O(n log n)
Karatsuba	T(n) = 3T(n/2) + O(n)	3, 2	O(n)	Case 1	O(n^1.585)
Strassen	T(n) = 7T(n/2) + O(n²)	7, 2	O(n²)	Case 1	O(n^2.807)
Stooge Sort	T(n) = 3T(2n/3) + O(1)	3, 3/2	O(1)	Case 1	O(n^2.71)

Understanding Combine Impact
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
"""
Analyzing how combine complexity affects overall runtime.
 
We'll compare three D&C algorithms for computing the sum of an array:
1. O(1) combine: Return sum of subsums (optimal)
2. O(n) combine: Unnecessarily iterate to sum (suboptimal)
3. O(n²) combine: Nested loop (very suboptimal)
"""
 
def sum_efficient(arr: list[int], left: int, right: int) -> int:
    """
    D&C sum with O(1) combine.
    
    Recurrence: T(n) = 2T(n/2) + O(1)
    Using Master Theorem: a=2, b=2, f(n)=O(1)
    c = log_2(2) = 1
    f(n) = O(1) = O(n^(1-1)) = O(n^0) = O(n^(c-ε)) for ε=1-0=1
    Case 1: T(n) = Θ(n^c) = Θ(n)
    """
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_sum = sum_efficient(arr, left, mid)
    right_sum = sum_efficient(arr, mid + 1, right)
    return left_sum + right_sum  # O(1) combine
 
 
def sum_inefficient(arr: list[int], left: int, right: int) -> int:
    """
    D&C sum with wasteful O(n) combine.
    
    Recurrence: T(n) = 2T(n/2) + O(n)
    Using Master Theorem: a=2, b=2, f(n)=O(n)
    c = log_2(2) = 1
    f(n) = Θ(n^1) = Θ(n^c)
    Case 2: T(n) = Θ(n^c · log n) = Θ(n log n)
    
    Much worse than necessary!
    """
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_sum = sum_inefficient(arr, left, mid)
    right_sum = sum_inefficient(arr, mid + 1, right)
    
    # Wasteful O(n) combine: iterate through range
    total = 0
    for i in range(left, right + 1):  # Unnecessary!
        total += arr[i]
    return total  # Could have just returned left_sum + right_sum
 
 
def sum_very_inefficient(arr: list[int], left: int, right: int) -> int:
    """
    D&C sum with extremely wasteful O(n²) combine.
    
    Recurrence: T(n) = 2T(n/2) + O(n²)
    Using Master Theorem: a=2, b=2, f(n)=O(n²)
    c = log_2(2) = 1
    f(n) = Ω(n^2) = Ω(n^(1+1)) = Ω(n^(c+ε)) for ε=1
    Case 3: T(n) = Θ(f(n)) = Θ(n²)
    
    Combine dominates completely!
    """
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_sum = sum_very_inefficient(arr, left, mid)
    right_sum = sum_very_inefficient(arr, mid + 1, right)
    
    # Absurdly wasteful O(n²) combine: nested loops
    total = 0
    for i in range(left, right + 1):
        for j in range(left, right + 1):  # Completely unnecessary
            if i == j:
                total += arr[i]
    return total
 
 
import time
 
def benchmark(func, arr, left, right, name):
    start = time.perf_counter()
    result = func(arr, left, right)
    elapsed = (time.perf_counter() - start) * 1000
    print(f"{name}: result={result}, time={elapsed:.3f}ms")
 
 
# Test with array of size 1000
test_arr = list(range(1000))
n = len(test_arr)
 
print("Benchmarking combine complexity impact:")
print("=" * 50)
benchmark(sum_efficient, test_arr, 0, n-1, "O(1) combine → O(n)")
benchmark(sum_inefficient, test_arr, 0, n-1, "O(n) combine → O(n log n)")
# sum_very_inefficient is too slow for size 1000, use smaller
benchmark(sum_very_inefficient, list(range(100)), 0, 99, "O(n²) combine → O(n²)")

Optimize the Combine Step

Since combine cost directly affects overall complexity, it's often the best place to optimize. Reducing O(n²) combine to O(n) can change the entire algorithm from quadratic to O(n log n). The work-per-level argument makes this clear: O(n) at each of log(n) levels gives O(n log n) total.

Implicit vs. Explicit Combination

Some D&C algorithms have explicit combine steps that perform visible work. Others have implicit combination where the solved subproblems are already the answer.

Explicit Combination:

The combine step does measurable work to integrate solutions.

Examples:

Merge sort: Explicit merge of two sorted arrays
Maximum subarray: Explicit cross-boundary calculation
Closest pair: Explicit checking of cross-strip pairs

Implicit Combination:

The solution is already in place after solving subproblems. No additional combine work is needed.

Examples:

Binary search: The found index IS the answer
Quicksort: After partitioning and sorting partitions, array is sorted
In-place tree modifications: Modifying subtrees modifies the whole tree

Explicit Combine (Merge Sort)
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # EXPLICIT COMBINE
    # This is visible work that
    # must happen after recursion
    return merge(left, right)
 
 
def merge(left, right):
    result = []
    i = j = 0
    # O(n) explicit work
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Implicit Combine (Quicksort)
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def quicksort(arr, left, right):
    if left >= right:
        return
    
    # DIVIDE does the work
    pivot_idx = partition(arr, left, right)
    
    # Conquer
    quicksort(arr, left, pivot_idx - 1)
    quicksort(arr, pivot_idx + 1, right)
    
    # IMPLICIT COMBINE
    # No code here! After both
    # recursive calls complete,
    # arr[left:right+1] is sorted.
    # The partitioning ensured this.
 
 
def partition(arr, left, right):
    pivot = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1

Trade-offs:

Aspect	Explicit Combine	Implicit Combine
Clarity	Steps are obvious	Logic may be subtle
Space	Often needs auxiliary space	Can be in-place
Parallelism	Combine must wait for children	May have better locality
Cache	May copy data repeatedly	Often better cache behavior

Choosing Between Them:

Implicit combination is elegant when the divide step arranges data so that solving subproblems automatically solves the whole problem. Use explicit combination when subproblem solutions need active integration.

Both Are Valid D&C

Algorithms with implicit combination are still D&C algorithms. The 'combine step' just happens to be O(1) or trivial. Don't think that D&C requires explicit merge-style operations. The paradigm is about the structure, not the combine complexity.

Designing Combine Steps

When designing a D&C algorithm for a novel problem, the combine step often requires the most creativity. Here's a framework for designing effective combine steps.

Step 1: Characterize Subproblem Solutions

What form does a subproblem solution take?

A single value (max, sum, count)?
A data structure (sorted array, tree)?
A set of candidates (points, intervals)?

Step 2: Identify What's Missing

After solving subproblems, what information is NOT captured?

Cross-boundary solutions?
Interactions between subproblem elements?
Global properties that require both halves?

Step 3: Design the Integration

How do we synthesize the final answer?

Simple aggregation (add, max, count)?
Merging ordered data?
Checking cross-boundary cases?

Step 4: Analyze Complexity

What's the cost of your combine step?

Is it O(1)? Great—recursion dominates.
Is it O(n)? That's often optimal for D&C.
Is it O(n²)? Consider if there's a more efficient approach.

Step 5: Verify Correctness

Prove that if subproblem solutions are correct, the combined solution is correct. This is the inductive step of your correctness proof.

Design Exercise: Count InversionsAn inversion is a pair (i,j) where i < j but arr[i] > arr[j]. Let's design the combine step for counting inversions using D&C.

Input

Output

Count Inversions: Designed Combine Step
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def count_inversions(arr: list[int]) -> tuple[list[int], int]:
    """
    Count inversions using D&C with carefully designed combine.
    
    Returns: (sorted array, inversion count)
    """
    if len(arr) <= 1:
        return (arr[:], 0)
    
    mid = len(arr) // 2
    
    # Conquer: Get sorted halves and inversion counts
    sorted_left, left_inv = count_inversions(arr[:mid])
    sorted_right, right_inv = count_inversions(arr[mid:])
    
    # Combine: Merge and count cross-inversions
    merged = []
    cross_inv = 0
    i = j = 0
    
    while i < len(sorted_left) and j < len(sorted_right):
        if sorted_left[i] <= sorted_right[j]:
            merged.append(sorted_left[i])
            i += 1
        else:
            merged.append(sorted_right[j])
            j += 1
            # KEY INSIGHT: sorted_left[i] > sorted_right[j]
            # All remaining elements in sorted_left (from i onwards)
            # are also > sorted_right[j] (because sorted_left is sorted)
            # Each forms an inversion with sorted_right[j]
            cross_inv += len(sorted_left) - i
    
    merged.extend(sorted_left[i:])
    merged.extend(sorted_right[j:])
    
    # Total inversions = within left + within right + cross boundary
    total_inv = left_inv + right_inv + cross_inv
    
    return (merged, total_inv)
 
 
# Test
arr = [2, 4, 1, 3, 5]
# Inversions: (2,1), (4,1), (4,3) = 3
sorted_arr, inversions = count_inversions(arr)
print(f"Sorted: {sorted_arr}")
print(f"Inversions: {inversions}")  # 3

Summary: Combining Solutions

We've explored the COMBINE phase of D&C in depth. Let's consolidate the key principles:

Key Takeaways

•Combine synthesizes partial solutions — It integrates subproblem results into a complete solution for the original problem.
•Common patterns exist — Trivial (O(1)), aggregation, merge (O(n)), and complex recombination patterns cover most cases.
•Merge is the workhorse of D&C — Many algorithms use O(n) merge, contributing to O(n log n) overall complexity.
•Cross-boundary cases require attention — Solutions spanning the division point need explicit handling in combine.
•Combine complexity affects overall runtime — The Master Theorem quantifies how f(n) impacts T(n).
•Implicit combine is valid — Some algorithms have trivial O(1) combine where the work happens in divide.
•Design from subproblem solutions — Characterize what subproblems return, identify what's missing, design the integration.
•Verify correctness — Prove that correct subproblem solutions yield correct combined solutions.

Module Complete:

With this page, we've completed our exploration of the D&C paradigm's three phases: Divide, Conquer, and Combine. You now have a comprehensive understanding of what Divide and Conquer is, how it works at each phase, and why it produces efficient algorithms.

What's Next:

In the following modules, we'll see D&C applied to specific problem domains: sorting algorithms (merge sort, quicksort), recurrence relations and the Master Theorem for complexity analysis, and classic D&C applications like maximum subarray, matrix multiplication, and closest pair of points.

Module Complete

Congratulations! You've mastered the foundational concepts of Divide and Conquer. You understand the paradigm's definition, the three-phase structure, and the principles governing each phase. You're ready to apply D&C to specific algorithms and analyze their complexity using the tools developed here.

4 / 4

Loading learning content...

Data Structures & AlgorithmsDivide and Conquer

What Is Divide and Conquer?

LevelIntermediate

Duration60 mins

TopicDivide and Conquer

4 / 4

Combining Solutions

The Final Assembly

The combine phase varies dramatically across D&C algorithms:

In binary search, combination is trivial: just return the result from the single explored subproblem
In quicksort, combination is implicit: partitioned elements are already in correct relative positions
In merge sort, combination is the heavy lift: merging two sorted arrays requires O(n) careful work
In Strassen's matrix multiplication, combination involves adding and subtracting submatrices in a specific pattern

What You Will Learn

The Role of the Combine Step

The combine step serves a critical function: it synthesizes partial solutions into a complete solution. Without correct combination, even perfectly solved subproblems yield wrong answers.

What Combination Must Achieve:

Correctness: The combined solution must correctly solve the original problem, given correct subproblem solutions
Completeness: No information from subproblem solutions should be lost or misrepresented
Efficiency: The combine step should not dominate the algorithm's complexity unnecessarily

The Combine Step in the Big Picture:

Recall the D&C recurrence:

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

Here, f(n) represents the combined cost of the divide and combine steps. In many algorithms:

Divide is O(1) or O(n)
Combine is O(1) to O(n²) depending on the algorithm

The relative cost of f(n) compared to the recursive work (a·T(n/b)) determines the overall complexity via the Master Theorem:

If f(n) is small: recursion dominates
If f(n) is large: combine/divide dominates
If balanced: all levels contribute equally

Combine Complexity in Classic D&C Algorithms
Algorithm	Divide Cost	Combine Cost	Overall Complexity
Binary Search	O(1)	O(1)	O(log n)
Merge Sort	O(1)	O(n) merge	O(n log n)
Quicksort	O(n) partition	O(1)	O(n log n) average
Maximum Subarray (D&C)	O(1)	O(n) cross-boundary	O(n log n)
Karatsuba Multiplication	O(n)	O(n) additions	O(n^1.585)
Strassen's Matrix Mult	O(n²)	O(n²) additions	O(n^2.807)

Where Does the Work Happen?

Common Combination Patterns

Most combine steps fall into recognizable patterns. Learning these patterns helps you design combine steps for novel problems.

Pattern 1: Trivial Combination (O(1))

The simplest case: subproblem solutions are already the full solution, or require minimal work to assemble.

Examples:

Binary search: Return the index found in a subproblem
Quicksort: Partitioned array is already in order (implicit combination)
Finding maximum: Return max of two subproblem maxima

# Maximum via D&C: O(1) combine
def max_dnc(arr, left, right):
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_max = max_dnc(arr, left, mid)
    right_max = max_dnc(arr, mid + 1, right)
    return max(left_max, right_max)  # O(1) combination!

Pattern 2: Aggregation (O(1) or O(k) where k is small)

Combine by applying an associative operation (sum, product, min, max, count, etc.).

Examples:

Sum array: Add subproblem sums
Count inversions: Add subproblem counts plus cross-boundary count
Tree size: Sum of subtree sizes plus one

# Sum via D&C: O(1) combine
def sum_dnc(arr, left, right):
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_sum = sum_dnc(arr, left, mid)
    right_sum = sum_dnc(arr, mid + 1, right)
    return left_sum + right_sum  # O(1) aggregation

Pattern 3: Merge (O(n))

Combine by interleaving or merging subproblem solutions based on their elements.

Examples:

Merge sort: Merge two sorted arrays into one
Maximum crossing subarray: Scan from midpoint in both directions
Closest pair: Check cross-boundary pairs

This pattern involves examining every element at each level, contributing O(n) work per level and O(n log n) total.

Merge Pattern: O(n) Combine
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def merge(left: list[int], right: list[int]) -> list[int]:
    """
    Classic O(n) merge operation.
    
    Combines two sorted lists by comparing heads and advancing.
    Total comparisons: at most len(left) + len(right) - 1
    """
    result = []
    i = j = 0
    
    # Compare and advance until one list is exhausted
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Append remaining elements (no comparisons needed)
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result
 
 
# Analysis:
# - Each element is appended exactly once: O(n)
# - Each comparison advances at least one pointer: at most n-1 comparisons
# - Total: O(n) time, O(n) auxiliary space

Pattern 4: Complex Recombination (O(n²) or specialized)

Some algorithms require sophisticated combination logic:

Examples:

Strassen's algorithm: Add/subtract specific submatrices
FFT: Combine using roots of unity
Convex hull: Merge hulls along tangent lines

These patterns often arise in algorithms that achieve subquadratic complexity for traditionally quadratic problems.

The Merge Operation: A Deep Dive

The merge operation is the most common non-trivial combine pattern. Understanding it deeply pays dividends across many D&C algorithms.

The Merge Invariant:

At each step of merging two sorted arrays A and B into result R:

All elements added to R are in sorted order
The next smallest unprocessed element is at A[i] or B[j]
Choosing min(A[i], B[j]) maintains sortedness

Why Merge is O(n):

Each comparison either:

Adds an element from A to R (advances i), or
Adds an element from B to R (advances j)

Total elements added: |A| + |B| = n Total comparisons: at most n - 1 (when arrays interleave perfectly)

Space-Time Tradeoff in Merge:

Standard merge uses O(n) auxiliary space. In-place merging is possible but complex:

Simple in-place approaches are O(n²)
Sophisticated in-place merge (block merging) is O(n) but with huge constants
In practice, O(n) auxiliary space is almost always preferred

Merge Sort with Detailed Combine Phase
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def merge_sort_detailed(arr: list[int]) -> list[int]:
    """
    Merge sort with detailed combine phase analysis.
    """
    
    def merge_sort_helper(arr: list[int], depth: int) -> list[int]:
        # Track work at each level
        indent = "  " * depth
        
        # Base case
        if len(arr) <= 1:
            return arr[:]
        
        # Divide
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        # Conquer
        sorted_left = merge_sort_helper(left, depth + 1)
        sorted_right = merge_sort_helper(right, depth + 1)
        
        # Combine (merge)
        result = []
        i = j = 0
        comparisons = 0
        
        while i < len(sorted_left) and j < len(sorted_right):
            comparisons += 1
            if sorted_left[i] <= sorted_right[j]:
                result.append(sorted_left[i])
                i += 1
            else:
                result.append(sorted_right[j])
                j += 1
        
        result.extend(sorted_left[i:])
        result.extend(sorted_right[j:])
        
        print(f"{indent}Merged {sorted_left} + {sorted_right}")
        print(f"{indent}  → {result} ({comparisons} comparisons)")
        
        return result
    
    return merge_sort_helper(arr, 0)
 
 
# Run with analysis
print("Merge Sort Combine Phase Analysis")
print("=" * 50)
result = merge_sort_detailed([38, 27, 43, 3, 9, 82, 10])
print(f"
Final result: {result}")

Output demonstration:

Merge Sort Combine Phase Analysis
==================================================
      Merged [38] + [27]
        → [27, 38] (1 comparisons)
      Merged [43] + [3]
        → [3, 43] (1 comparisons)
    Merged [27, 38] + [3, 43]
      → [3, 27, 38, 43] (3 comparisons)
      Merged [9] + [82]
        → [9, 82] (1 comparisons)
      Merged [9, 82] + [10]
        → [9, 10, 82] (2 comparisons)
  Merged [3, 27, 38, 43] + [9, 10, 82]
    → [3, 9, 10, 27, 38, 43, 82] (6 comparisons)

Final result: [3, 9, 10, 27, 38, 43, 82]

Notice how:

Deepest merges happen first (bottom-up in the recursion tree)
Comparison count scales with merge size
Total work per level sums to O(n)

Stability Through Merge

Handling Cross-Boundary Cases

Many D&C algorithms have solutions that span the boundary between subproblems. These cross-boundary cases require explicit handling in the combine step.

The Cross-Boundary Problem:

When dividing a problem at a midpoint, some solutions might:

Start in the left subproblem and end in the right subproblem
Depend on elements from both sides simultaneously
Not be captured by either subproblem alone

Example: Maximum Subarray Sum

Consider finding the maximum sum contiguous subarray:

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Midpoint: after index 3 (after value 4)

The answer is [4, -1, 2, 1] with sum 6.
This subarray SPANS the midpoint!

Left subproblem thinks max is [1] = 1
Right subproblem thinks max is [4] = 4
Neither alone finds the cross-boundary answer of 6

Solution Strategy:

Explicitly find the best cross-boundary solution during the combine step:

Find best suffix of left subproblem (ending at midpoint)
Find best prefix of right subproblem (starting just after midpoint)
Combine them (they share the boundary, so concatenation is valid)
Compare cross-boundary result with subproblem results

Maximum Subarray with Cross-Boundary Handling
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def max_subarray(arr: list[int], left: int, right: int) -> tuple[int, int, int]:
    """
    Find maximum subarray using D&C with cross-boundary handling.
    
    Returns: (max_sum, start_index, end_index)
    """
    # Base case: single element
    if left == right:
        return (arr[left], left, left)
    
    mid = (left + right) // 2
    
    # CONQUER: Find max subarray in each half
    left_max, left_start, left_end = max_subarray(arr, left, mid)
    right_max, right_start, right_end = max_subarray(arr, mid + 1, right)
    
    # COMBINE: Find max crossing subarray
    cross_sum, cross_start, cross_end = max_crossing(arr, left, mid, right)
    
    # Return the best of three candidates
    if left_max >= right_max and left_max >= cross_sum:
        return (left_max, left_start, left_end)
    elif right_max >= left_max and right_max >= cross_sum:
        return (right_max, right_start, right_end)
    else:
        return (cross_sum, cross_start, cross_end)
 
 
def max_crossing(arr: list[int], left: int, mid: int, right: int) -> tuple[int, int, int]:
    """
    Find maximum subarray that must cross the midpoint.
    
    Key insight: Such a subarray is the concatenation of:
    - Best suffix of left half (ending at mid)
    - Best prefix of right half (starting at mid+1)
    """
    # Find best suffix of left half
    left_sum = float('-inf')
    current = 0
    max_left_idx = mid
    for i in range(mid, left - 1, -1):  # Go from mid backwards
        current += arr[i]
        if current > left_sum:
            left_sum = current
            max_left_idx = i
    
    # Find best prefix of right half
    right_sum = float('-inf')
    current = 0
    max_right_idx = mid + 1
    for i in range(mid + 1, right + 1):  # Go from mid+1 forwards
        current += arr[i]
        if current > right_sum:
            right_sum = current
            max_right_idx = i
    
    return (left_sum + right_sum, max_left_idx, max_right_idx)
 
 
# Test
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, start, end = max_subarray(arr, 0, len(arr) - 1)
print(f"Maximum sum: {max_sum}")
print(f"Subarray: {arr[start:end+1]} (indices {start} to {end})")
# Output:
# Maximum sum: 6
# Subarray: [4, -1, 2, 1] (indices 3 to 6)

Cross-Boundary in Other Algorithms:

Closest pair of points: After finding closest pairs within each half, must check pairs crossing the dividing line. Uses clever observation that only O(n) pairs need checking.
Counting inversions: Inversions within each half are counted recursively. Cross-boundary inversions are counted during merge: each time we pick from the right array, we count how many left-array elements remain.
Convex hull (merge): Individual hulls are found recursively. Merging requires finding upper and lower tangent lines between hulls.

Don't Forget Cross-Boundary Cases

Combine Complexity and the Master Theorem

The combine step's complexity directly impacts the overall D&C algorithm complexity. Understanding this relationship requires the Master Theorem.

The D&C Recurrence:

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

Where:

a = number of subproblems (typically 2 in binary D&C)
b = factor by which input shrinks (typically 2 for halving)
f(n) = cost of divide + combine (often dominated by combine)

Master Theorem Cases (simplified):

Let c = log_b(a) (the critical exponent)

If f(n) = O(n^(c-ε)): Recursion dominates → T(n) = Θ(n^c)
If f(n) = Θ(n^c · log^k n): Balanced → T(n) = Θ(n^c · log^(k+1) n)
If f(n) = Ω(n^(c+ε)): Combine dominates → T(n) = Θ(f(n))

Master Theorem Applied to Common D&C
Algorithm	Recurrence	a, b	f(n)	Case	Result
Binary Search	T(n) = T(n/2) + O(1)	1, 2	O(1)	Case 2 (k=0)	O(log n)
Merge Sort	T(n) = 2T(n/2) + O(n)	2, 2	O(n)	Case 2 (k=0)	O(n log n)
Karatsuba	T(n) = 3T(n/2) + O(n)	3, 2	O(n)	Case 1	O(n^1.585)
Strassen	T(n) = 7T(n/2) + O(n²)	7, 2	O(n²)	Case 1	O(n^2.807)
Stooge Sort	T(n) = 3T(2n/3) + O(1)	3, 3/2	O(1)	Case 1	O(n^2.71)

Understanding Combine Impact
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
"""
Analyzing how combine complexity affects overall runtime.
 
We'll compare three D&C algorithms for computing the sum of an array:
1. O(1) combine: Return sum of subsums (optimal)
2. O(n) combine: Unnecessarily iterate to sum (suboptimal)
3. O(n²) combine: Nested loop (very suboptimal)
"""
 
def sum_efficient(arr: list[int], left: int, right: int) -> int:
    """
    D&C sum with O(1) combine.
    
    Recurrence: T(n) = 2T(n/2) + O(1)
    Using Master Theorem: a=2, b=2, f(n)=O(1)
    c = log_2(2) = 1
    f(n) = O(1) = O(n^(1-1)) = O(n^0) = O(n^(c-ε)) for ε=1-0=1
    Case 1: T(n) = Θ(n^c) = Θ(n)
    """
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_sum = sum_efficient(arr, left, mid)
    right_sum = sum_efficient(arr, mid + 1, right)
    return left_sum + right_sum  # O(1) combine
 
 
def sum_inefficient(arr: list[int], left: int, right: int) -> int:
    """
    D&C sum with wasteful O(n) combine.
    
    Recurrence: T(n) = 2T(n/2) + O(n)
    Using Master Theorem: a=2, b=2, f(n)=O(n)
    c = log_2(2) = 1
    f(n) = Θ(n^1) = Θ(n^c)
    Case 2: T(n) = Θ(n^c · log n) = Θ(n log n)
    
    Much worse than necessary!
    """
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_sum = sum_inefficient(arr, left, mid)
    right_sum = sum_inefficient(arr, mid + 1, right)
    
    # Wasteful O(n) combine: iterate through range
    total = 0
    for i in range(left, right + 1):  # Unnecessary!
        total += arr[i]
    return total  # Could have just returned left_sum + right_sum
 
 
def sum_very_inefficient(arr: list[int], left: int, right: int) -> int:
    """
    D&C sum with extremely wasteful O(n²) combine.
    
    Recurrence: T(n) = 2T(n/2) + O(n²)
    Using Master Theorem: a=2, b=2, f(n)=O(n²)
    c = log_2(2) = 1
    f(n) = Ω(n^2) = Ω(n^(1+1)) = Ω(n^(c+ε)) for ε=1
    Case 3: T(n) = Θ(f(n)) = Θ(n²)
    
    Combine dominates completely!
    """
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    left_sum = sum_very_inefficient(arr, left, mid)
    right_sum = sum_very_inefficient(arr, mid + 1, right)
    
    # Absurdly wasteful O(n²) combine: nested loops
    total = 0
    for i in range(left, right + 1):
        for j in range(left, right + 1):  # Completely unnecessary
            if i == j:
                total += arr[i]
    return total
 
 
import time
 
def benchmark(func, arr, left, right, name):
    start = time.perf_counter()
    result = func(arr, left, right)
    elapsed = (time.perf_counter() - start) * 1000
    print(f"{name}: result={result}, time={elapsed:.3f}ms")
 
 
# Test with array of size 1000
test_arr = list(range(1000))
n = len(test_arr)
 
print("Benchmarking combine complexity impact:")
print("=" * 50)
benchmark(sum_efficient, test_arr, 0, n-1, "O(1) combine → O(n)")
benchmark(sum_inefficient, test_arr, 0, n-1, "O(n) combine → O(n log n)")
# sum_very_inefficient is too slow for size 1000, use smaller
benchmark(sum_very_inefficient, list(range(100)), 0, 99, "O(n²) combine → O(n²)")

Optimize the Combine Step

Implicit vs. Explicit Combination

Some D&C algorithms have explicit combine steps that perform visible work. Others have implicit combination where the solved subproblems are already the answer.

Explicit Combination:

The combine step does measurable work to integrate solutions.

Examples:

Merge sort: Explicit merge of two sorted arrays
Maximum subarray: Explicit cross-boundary calculation
Closest pair: Explicit checking of cross-strip pairs

Implicit Combination:

The solution is already in place after solving subproblems. No additional combine work is needed.

Examples:

Binary search: The found index IS the answer
Quicksort: After partitioning and sorting partitions, array is sorted
In-place tree modifications: Modifying subtrees modifies the whole tree

Explicit Combine (Merge Sort)
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # EXPLICIT COMBINE
    # This is visible work that
    # must happen after recursion
    return merge(left, right)
 
 
def merge(left, right):
    result = []
    i = j = 0
    # O(n) explicit work
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Implicit Combine (Quicksort)
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def quicksort(arr, left, right):
    if left >= right:
        return
    
    # DIVIDE does the work
    pivot_idx = partition(arr, left, right)
    
    # Conquer
    quicksort(arr, left, pivot_idx - 1)
    quicksort(arr, pivot_idx + 1, right)
    
    # IMPLICIT COMBINE
    # No code here! After both
    # recursive calls complete,
    # arr[left:right+1] is sorted.
    # The partitioning ensured this.
 
 
def partition(arr, left, right):
    pivot = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1

Trade-offs:

Aspect	Explicit Combine	Implicit Combine
Clarity	Steps are obvious	Logic may be subtle
Space	Often needs auxiliary space	Can be in-place
Parallelism	Combine must wait for children	May have better locality
Cache	May copy data repeatedly	Often better cache behavior

Choosing Between Them:

Both Are Valid D&C

Designing Combine Steps

When designing a D&C algorithm for a novel problem, the combine step often requires the most creativity. Here's a framework for designing effective combine steps.

Step 1: Characterize Subproblem Solutions

What form does a subproblem solution take?

A single value (max, sum, count)?
A data structure (sorted array, tree)?
A set of candidates (points, intervals)?

Step 2: Identify What's Missing

After solving subproblems, what information is NOT captured?

Cross-boundary solutions?
Interactions between subproblem elements?
Global properties that require both halves?

Step 3: Design the Integration

How do we synthesize the final answer?

Simple aggregation (add, max, count)?
Merging ordered data?
Checking cross-boundary cases?

Step 4: Analyze Complexity

What's the cost of your combine step?

Is it O(1)? Great—recursion dominates.
Is it O(n)? That's often optimal for D&C.
Is it O(n²)? Consider if there's a more efficient approach.

Step 5: Verify Correctness

Prove that if subproblem solutions are correct, the combined solution is correct. This is the inductive step of your correctness proof.

Design Exercise: Count InversionsAn inversion is a pair (i,j) where i < j but arr[i] > arr[j]. Let's design the combine step for counting inversions using D&C.

Input

Output

Count Inversions: Designed Combine Step
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def count_inversions(arr: list[int]) -> tuple[list[int], int]:
    """
    Count inversions using D&C with carefully designed combine.
    
    Returns: (sorted array, inversion count)
    """
    if len(arr) <= 1:
        return (arr[:], 0)
    
    mid = len(arr) // 2
    
    # Conquer: Get sorted halves and inversion counts
    sorted_left, left_inv = count_inversions(arr[:mid])
    sorted_right, right_inv = count_inversions(arr[mid:])
    
    # Combine: Merge and count cross-inversions
    merged = []
    cross_inv = 0
    i = j = 0
    
    while i < len(sorted_left) and j < len(sorted_right):
        if sorted_left[i] <= sorted_right[j]:
            merged.append(sorted_left[i])
            i += 1
        else:
            merged.append(sorted_right[j])
            j += 1
            # KEY INSIGHT: sorted_left[i] > sorted_right[j]
            # All remaining elements in sorted_left (from i onwards)
            # are also > sorted_right[j] (because sorted_left is sorted)
            # Each forms an inversion with sorted_right[j]
            cross_inv += len(sorted_left) - i
    
    merged.extend(sorted_left[i:])
    merged.extend(sorted_right[j:])
    
    # Total inversions = within left + within right + cross boundary
    total_inv = left_inv + right_inv + cross_inv
    
    return (merged, total_inv)
 
 
# Test
arr = [2, 4, 1, 3, 5]
# Inversions: (2,1), (4,1), (4,3) = 3
sorted_arr, inversions = count_inversions(arr)
print(f"Sorted: {sorted_arr}")
print(f"Inversions: {inversions}")  # 3

Summary: Combining Solutions

We've explored the COMBINE phase of D&C in depth. Let's consolidate the key principles:

Key Takeaways

•Combine synthesizes partial solutions — It integrates subproblem results into a complete solution for the original problem.
•Common patterns exist — Trivial (O(1)), aggregation, merge (O(n)), and complex recombination patterns cover most cases.
•Merge is the workhorse of D&C — Many algorithms use O(n) merge, contributing to O(n log n) overall complexity.
•Cross-boundary cases require attention — Solutions spanning the division point need explicit handling in combine.
•Combine complexity affects overall runtime — The Master Theorem quantifies how f(n) impacts T(n).
•Implicit combine is valid — Some algorithms have trivial O(1) combine where the work happens in divide.
•Design from subproblem solutions — Characterize what subproblems return, identify what's missing, design the integration.
•Verify correctness — Prove that correct subproblem solutions yield correct combined solutions.

Module Complete:

What's Next:

Module Complete

4 / 4