Divide and Conquer — Explained with Examples

Divide and conquer recursively splits a problem into independent subproblems, solves each, and combines results into the final solution.

Divide and conquer has three steps: divide the problem into smaller subproblems, conquer each subproblem recursively, and combine the subproblem solutions. Unlike dynamic programming, subproblems in divide and conquer are independent (no overlap). Classic examples include merge sort, quicksort, binary search, and the Fast Fourier Transform.

Think of divide and conquer like organizing a large conference. Instead of one person handling 1000 attendees, you divide into 10 groups of 100, assign each to a coordinator, who divides further into teams of 10. Each team lead reports up, and results combine into the final organized event.

Merge sort exemplifies the pattern: divide the array into halves, recursively sort each half, then merge the sorted halves. The merge step is where the real work happens — combining two sorted arrays 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(left, right):
    result = []
    i = j = 0
    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

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# Output: [3, 9, 10, 27, 38, 43, 82]

Divide and conquer is fundamental to parallel computing — independent subproblems can run on separate processors. It typically achieves O(n log n) time for sorting and O(log n) for search.

Recursion, Dynamic Programming, Sorting Algorithms, Big O

Sorting with Divide and Conquer