DSA Divide and Conquer

Divide and conquer solves a big problem by splitting it into smaller copies of the same problem. Each small copy gets solved on its own. The partial answers join together to form the final answer. Many of the fastest algorithms in computer science follow this plan.

Imagine a teacher with 100 exam papers to sort by score. Sorting all of them alone takes ages. The teacher hands 25 papers to each of four helpers. Every helper sorts a small pile, and the teacher merges the four sorted piles into one. The work finishes much faster.

The Three Steps

• Divide: break the problem into smaller parts of the same kind.
• Conquer: solve each part. Tiny parts get solved directly, and larger parts use recursion.
• Combine: join the partial answers into one complete answer.

Splitting Diagram

Problem of size 8

            [8 items]
           /          \
     [4 items]      [4 items]
      /    \          /    \
  [2]      [2]     [2]      [2]
  / \      / \     / \      / \
[1] [1]  [1] [1] [1] [1]  [1] [1]

Size 1 is easy. Answers merge upward.

Example: Find the Largest Number

The method splits the list in half, finds the largest in each half, and keeps the bigger result.

def find_max(items, low, high):
    if low == high:
        return items[low]
    mid = (low + high) // 2
    left_max = find_max(items, low, mid)
    right_max = find_max(items, mid + 1, high)
    return max(left_max, right_max)

data = [7, 2, 9, 4, 6, 1]
print(find_max(data, 0, len(data) - 1))   # 9

Example: Merge Sort

Merge sort stands as the classic case. The list splits down to single items, which are already sorted. Merging two sorted lists builds longer sorted lists.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[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]))
# [3, 9, 10, 27, 38, 43, 82]

[38, 27, 43, 3]
  split -> [38, 27] [43, 3]
  split -> [38] [27] [43] [3]
  merge -> [27, 38] [3, 43]
  merge -> [3, 27, 38, 43]

Example: Fast Power

Computing 2 to the power of 10 by multiplying ten times works but wastes effort. Halving the exponent cuts the work sharply.

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x

print(power(2, 10))   # 1024

power(2, 10) = power(2, 5)^2
power(2, 5)  = power(2, 2)^2 * 2
power(2, 2)  = power(2, 1)^2
power(2, 1)  = power(2, 0)^2 * 2
power(2, 0)  = 1

The method needs about log n multiplications instead of n.

Counting the Cost

Merge sort splits the list into 2 halves and spends O(n) time merging. That pattern gives the rule T(n) = 2T(n/2) + O(n). The list halves about log n times, and each level of splitting costs O(n) in total work. Multiplying the two gives O(n log n). Fast power makes one smaller call per step, so its cost is O(log n).

Divide and Conquer vs Dynamic Programming

Divide and conquer works best when the small parts do not overlap. Merge sort never solves the same sub-list twice. Dynamic programming handles problems where the small parts repeat, and it stores answers to avoid recomputing them.

Spotting the Pattern

Ask whether the answer for the whole list can come from the answers for two halves. A maximum, a sorted order, and a power all pass that test. Problems that need information from every item at once, such as a running total with a custom rule, may fit another method better.

Real-Life Uses

Sorting libraries in many languages rely on merge sort or quicksort, both divide and conquer methods. Binary search halves the search space each step. Image tools split a large picture into tiles and process the tiles in parallel. Large-scale data jobs split work across many machines and merge the results.

Key Points

• Divide and conquer splits, solves, and combines.
• Each part is a smaller copy of the original problem.
• Merge sort runs in O(n log n) time.
• Fast power finishes in O(log n) time.
• A clear base case stops the recursion.
• The method suits problems whose parts do not overlap.