juniorDivide & Conquer

Explain the three main steps of Divide and Conquer.

Updated Apr 28, 2026

Short answer

Divide and Conquer is an algorithm design technique that solves problems by breaking them into smaller subproblems, solving those subproblems, and combining their results. The three main steps are Divide, Conquer, and Combine. Algorithms like Merge Sort and Binary Search use this approach to efficiently solve large problems.

Deep explanation

Divide and Conquer works by reducing a large problem into smaller, easier-to-solve versions of the same problem. The process has three main steps:

  1. Divide
  2. Conquer
  3. Combine

---

1. Divide

The first step is to break the original problem into smaller subproblems.

The goal is to create smaller instances that are easier to solve. Usually, the subproblems are similar to the original problem but have a smaller input size.

Example with Merge Sort:

TEXT
Original array:


[8, 3, 5, 1, 9, 2]


Divide:


[8, 3, 5]    [1, 9, 2]


Divide again:


[8] [3, 5]   [1] [9, 2]

The algorithm continues dividing until reaching a simple case that can be solved directly.

---

2. Conquer

The second step is solving the smaller subproblems.

Usually, this is done recursively by applying the same algorithm to each smaller piece.

Example:

TEXT
[8, 3, 5]


becomes:


[8] [3] [5]

At this point, each single-element array is already sorted, so the problem is considered solved.

The stopping point is called the base case.

A good base case:

  • Stops the recursion.
  • Solves the smallest possible input directly.
  • Allows results to be returned back up the recursion chain.

---

3. Combine

The final step is combining the solutions of the smaller subproblems to create the solution to the original problem.

Example in Merge Sort:

TEXT
Sorted smaller arrays:


[3, 8] and [1, 5]


Combine:


[1, 3, 5, 8]

The combine step depends on the problem:

  • Merge Sort combines sorted arrays.
  • Binary Search does not need a combine step because it only follows one half.
  • Some mathematical algorithms combine partial results using addition or multiplication.

---

Complete Divide and Conquer Flow

The overall process looks like this:

TEXT
Problem
                   |
                Divide
              /        \
        Subproblem   Subproblem
             |            |
          Conquer      Conquer
             \            /
              \          /
               Combine
                   |
              Final Solution

---

Example: Merge Sort

Merge Sort demonstrates all three steps:

Python
def merge_sort(arr):
    # Base case: Conquer directly
    if len(arr) <= 1:
        return arr


    # Divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])


    # Combine
    return merge(left, right)

The algorithm:

  1. Divides the array into halves.
  2. Recursively sorts each half.
  3. Merges the sorted halves.

---

Advantages of Divide and Conquer

  • Reduces complex problems into smaller manageable parts.
  • Often improves time complexity.
  • Works naturally with recursion.
  • Can enable parallel processing because subproblems are independent.

Disadvantages

  • Recursive calls can add memory overhead.
  • Combining solutions can be complex.
  • Poorly designed splits may reduce efficiency.

---

Real-world example

A search engine may need to process a huge collection of documents. Instead of analyzing all documents at once, it can divide the work into smaller groups, process each group independently, and combine the results.

A simplified example:

Python
def count_documents(documents):
    if len(documents) <= 1:
        return len(documents)


    mid = len(documents) // 2


    left = count_documents(documents[:mid])
    right = count_documents(documents[mid:])


    return left + right

Here:

  • Divide: Split documents into two groups.
  • Conquer: Count documents in each group.
  • Combine: Add the two counts together.

Common mistakes

  • * Confusing Divide and Conquer with Dynamic Programming.
  • * Forgetting that the subproblems should usually be smaller versions of the same problem.
  • * Ignoring the base case that stops recursion.
  • * Assuming every recursive algorithm is a Divide and Conquer algorithm.
  • * Forgetting the combine step when explaining the approach.
  • * Splitting the problem into subproblems that are not easier to solve.
  • * Assuming Divide and Conquer always improves performance.
  • * Ignoring the cost of combining subproblem solutions.

Follow-up questions

  • What are the three steps of a Divide and Conquer algorithm?
  • How is Divide and Conquer different from Dynamic Programming?
  • Which algorithms use the Divide and Conquer approach?
  • Why is the base case important in Divide and Conquer?
  • Does every Divide and Conquer algorithm require a combine step?
  • What makes a Divide and Conquer solution efficient?

More Divide & Conquer interview questions

View all →