In a Divide and Conquer Paradigm we divide the bigger problem into smaller sub problems and call the function recursively to solve the sub problems. Divide and Conquer method is more appropriate for those problems that have polynomial time solutions. Some of the Divide and Conquer Algorithms are Insertion sort, bubble sort, etc. Read this to know more about this algorithms HERE

**Divide and Conquer Paradigm. 3 – Steps**

**Divide. **Divide the bigger Problem into smaller sub problems.

**Conquer. **Solve the sub problems recursively, if the sub problem is very small then solve it in straight-forward manner.

**Combine. **combine all the solutions into the solutions of original problem.

**Merge Sort**

**Problem: **Given an array of size n, sort them in ascending order.

**Solution**

- Divide the n elements into the n/2 subarrays.
- Sort the two subarrays in recursively.
- Merge the two subarrays into the sorted array

**Algorithm of Merge Sort**

*
Sort:*
* If len(array) > 1:
s = len(array)/2
A = array - 0 to A
B = array - A to len(array)
Sort(A)
Sort(B)
c = Merge(A,B)
return c
*

*Merge:
len_c = len(A) + len(B)
i = 0 j = 0
for k = 0 to Len_c
if A[i] <= B[j]
C[k] = A[i]
i = i + 1
else:
C[k] = B[j]
j = j + 1
return C*

**Time Complexity **

Time complexity of the algorithm is **nlog2n **where the base is 2. The time complexity of Merge function is **O(n).**

log2n is the number of levels.

**Which Sorting Algorithm is of Divide and Conquer Type?**

**Def. **Any Algorithm which can Divide a bigger problem into smaller problems and give a combined solution is of Divide and Conquer type. Usually these have Time complexity in **logn**. In order to identify the Sorting algorithm as Divide and Conquer type you can look at is time complexity.

#### READ MORE

**Algorithms **related posts visit **HERE**

**Data Structures **related posts visit **HERE**

**Databases** related posts Visit **HERE**

**Python-related** posts Visit **HERE**

**C++** related posts Visit **HERE**

**Data Science** related posts visit **HERE**