Divide and Conquer Algorithm

This algorithm divides a problem recursively into 2 or more sub-problems of the same or similar type until they become a simple unit of operation. These sub-problems are then combined to solve a given problem.

Let’s see one of the implementations of the Divide-and-Conquer algorithm using mergeSort.

Visualization of the Divide-and-Conquer Algorithm.

key points visualization in Divide and Conquer Algorithm

1. Tail of green arrows are subarrays a1 and a2 of some particular recursive call in the
below question
2. That’s why we assumed subarrays a1 and a2 to be sorted.

#include<bits/stdc++.h> // It includes all the libraries
using namespace std;

void merge(int a[], int l, int r)
     int m = (l+r)/2;
     // s1 and s2 are two temp subarray's length.
     int s1 = m-l+1;
     int s2 = r-m;
     int a1[s1], a2[s2];

     // copy elements into temp arrays
     for(int i=0;i<s1;i++) a1[i] = a[l+i];
     for(int i=0;i<s2;i++) a2[i] = a[m+1+i];

     // Now we sort a[] from index l to r using temp arrays
     int i1=0,i2=0,i=l;
     while(i1<s1 && i2<s2 )
         if(a1[i1] < a2[i2]) a[i++] = a1[i1++]; // put the smaller element in a[]
         else a[i++] = a2[i2++]; 

     // corner case
     // There might be few elements left in a1[] or a2[]
     while(i1<s1) a[i++] = a1[i1++];
     while(i2<s2) a[i++] = a2[i2++];
     // Now our array a[] is sorted from index 'l' to 'r'
void mergeSort(int a[], int l, int r)
     if(l>=r) return; // Return for invalid case
     int m = (l+r)/2; // mid element
     // below two lines are the actual implementation of Divied & Conquer Algo
     // Because it recursively breaks down the problem into two sub problem of same type 
     mergeSort(a,l,m); // Dividing recursively, so O(logn)

     // This will sort a[] from index 'l' to 'r'
     merge(a,l,r); // linear operation in this call, so O(n)

     // Therefore overall complexity is O(n*logn)

int main()
   int a[n];// array to be sorted
   // calling mergeSort

   return 0;

Bonus: (some of the frequently asked questions in the interview)
1. Inversion count of an array
2. Quick sort

You might also like to check the following articles: