Scribd
Upload
27 views2 pages

How Divide and Conquer Algorithms Work

Divide and conquer algorithms involve three main steps: dividing the problem into smaller sub-problems, solving those sub-problems recursively, and combining their solutions to address the original problem. The document illustrates this process using merge sort, where an array is recursively divided into halves until individual elements are reached, and then combined in a sorted manner. This approach emphasizes the recursive nature of problem-solving in algorithms.

Uploaded by

Gagambi Tubyas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
27 views2 pages

How Divide and Conquer Algorithms Work

Divide and conquer algorithms involve three main steps: dividing the problem into smaller sub-problems, solving those sub-problems recursively, and combining their solutions to address the original problem. The document illustrates this process using merge sort, where an array is recursively divided into halves until individual elements are reached, and then combined in a sorted manner. This approach emphasizes the recursive nature of problem-solving in algorithms.

Uploaded by

Gagambi Tubyas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

How Divide and Conquer Algorithms

Work? Here are the steps involved:

1. Divide: Divide the given problem into sub-problems using recursion. 2.


Conquer: Solve the smaller sub-problems recursively. If the subproblem is
small enough, then solve it directly.
3. Combine: Combine the solutions of the sub-problems that are part of the
recursive process to solve the actual problem.
Here, we will sort an array using the divide and conquer approach (ie. merge
sort).

1. Let the given array be: Array for merge sort


2. Divide the array into two halves.

3. Divide the array into two subparts


Again, divide each subpart recursively into two halves until you get individual
elements.
Divide
the array into smaller subparts
4. Now, combine the individual elements in a sorted manner.
Here, conquer and combine steps go side by side.

Combine the subparts

You might also like