Divide and conquer is an algorithmic strategy works by breaking down a problem into two or more sub-problems of the same or related type, solving them and make an addition of the sub problems. Let make it clear. In divide and conquer technique we need to divide a problem into sub-problems , solving them recursively and combine the sub-problems. So we can assume that, to follow this strategy we need to divide a into some parts then conquer or solve the parts and finally combine them. Thus we can solve a problem easily.
There are many algorithms those follow divide and conquer technique. Such as Recursive Binary Search, Merge Sort, Quick sort, Selection sort, Strassen’s Matrix Multiplication etc.
I want to make a series in which I will discuss about some algorithms which follow divide and conquer strategy.
Today I am discussing about Merge Sort. Merge Sort is a sorting algorithm. In which we are following divide and conquer strategy. In Merge Sort we’ll divide an array into two parts, then sort them individually and finally combine them.
At first we need to input in an array. Then we’ll apply the following steps:
Step 1: If the array has not more than one elements then the array has already been sorted.
Step 2: Then we keep the half of the elements of the array in a new array named left and merge sorted them array.
Step 3: Then other half elements of array should kept in right array and merge sorted the array.
Step 4: Finally merge the two merge sorted array.
Let have an array having eight elements — 8,3,2,9,7,1,5,4. Now we will split them into two parts. Then we’ll follow the previous steps. By seeing these image you can get a clear explanation.
To apply these steps in a program firstly we need a merge sort program and then we’ll need a merge program. So let’s write the program.
Merge Sort function:
//ara is needed to merge sorted//left is the index of first element//right is the index of last element
void merge_sort (int ara[], int left, int right)
{
if(left >=right){
return;
}
//ara is divided into two parts
// one is from left to mid
// other is from mid+1 to right
int mid = left+(right-left)/2;//applying merge sort from ara[left] to ara[mid]merge_sort(ara,left,mid);//applying merge sort from ara[mid+1] to ara[right]merge_sort(ara,mid+1,right);//finally merging themmerge(ara,left,mid,right);
}
Then we need to make a Merge function.
void merge(int ara[],int left,int mid,int right){
int i;int index_a, index_l, index_r;int size_left, size_right;size_left = mid - left + 1;size_right = right - mid;int L [size_left], R[size_right];
//copying from ara\[left\] to ara\[mid\]
for(i=0;i<size\_left;i++)
{
L[i]=ara[left+i];
}
////copying from ara\[mid+1\] to ara\[right\]
for(i=0;i<size\_right;i++)
{
R[i]=ara[mid+1+i];
}index_l = 0;index_r = 0;for(index_a = left;index_l < size_left && index_r < size_right;index_a++){
if(L[index_l]<R[index_r]){
ara[index_a] = L[index_l];index_l += 1;
}else{
ara[index_a] = R [index_r];index_r += 1;
}
}
while (index_l < size_left){
ara[index_a] = L [index_l];index_l += 1;index_a += 1;
}while (index_r < size_right){
ara[index_a] = R [index_r];index_r += 1;index_a += 1;
}
}
Finally the program will be:
#include <iostream>
using namespace std;
void merge(int ara[],int left,int mid,int right);
//ara is needed to merge sorted//left is the index of first element//right is the index of last element
void merge_sort (int ara[], int left, int right)
{
if(left >=right){
return;
}
//ara is divided into two parts// one is from left to mid// other is from mid+1 to right
int mid = left+(right-left)/2;//applying merge sort from ara[left] to ara[mid]merge_sort(ara,left,mid);//applying merge sort from ara[mid+1] to ara[right]merge_sort(ara,mid+1,right);//finally merging themmerge(ara,left,mid,right);
}
void merge(int ara[],int left,int mid,int right){
int i;int index_a, index_l, index_r;int size_left, size_right;size_left = mid - left + 1;size_right = right - mid;int L [size_left], R[size_right];
//copying from ara[left] to ara[mid]for(i=0;i<size_left;i++){
L[i]=ara[left+i];
}
////copying from ara[mid+1] to ara[right]for(i=0;i<size_right;i++){
R[i]=ara[mid+1+i];
}index_l = 0;index_r = 0;for(index_a = left;index_l < size_left && index_r < size_right;index_a++){
if(L[index_l]<R[index_r]){
ara[index_a] = L[index_l];index_l += 1;
}else{
ara[index_a] = R [index_r];index_r += 1;
}
}
while (index_l < size_left){
ara[index_a] = L [index_l];index_l += 1;index_a += 1;
}while (index_r < size_right){
ara[index_a] = R [index_r];index_r += 1;index_a += 1;
}
}int main(){
int i, n = 7;int ara[] = {8,3,2,9,7,1,5,4};cout<<"After merge sorting:"<<endl;merge_sort(ara,0,n);for(i=0; i<=n; i++){
cout<<ara[i]<<endl;
}return 0;
}
We will get the output like this:
Complexity of Merge Sort:
Here we have divided the array into two parts. So the complexity of it is
O(log n). But we have merged them too. For the merge() function the complexity is O(n).
So the complexity of merge sort is O((log n) x n) or O(n log n).
Happy coding!
Reference:
Computer Programming by Tamim Shahriar Subeen
The Bangla programming books of dimik has changed my life.
Thanks to Tamim Shahriar Subeen Vaiya :) .