Which Sorting Algorithm is of Divide and Conquer Type

by

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
which sorting algorithm is of divide and conquer type

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

Leave a Comment