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.
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)
mergeSort(a,m+1,r);
// 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
mergeSort(a,0,n-1);
return 0;
}
Bonus: (some of the frequently asked questions in the interview)
1. Inversion count of an array
2. Quick sort