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.

![](https://hackernoon.com/hn-images/1*zsMWBmP_fY4Dl40fHSnDaw.png)

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 them  
    merge(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 them  
    merge(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:

![](https://hackernoon.com/hn-images/1*1XkvF-qR1eGstxuwp_12fw.png)

**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](http://dimik.pub/book/245/computer-programming-3-data-structure-algorithm-by-tamim-shahriar) by [Tamim Shahriar Subeen](https://medium.com/@subeen)

The Bangla programming books of dimik has changed my life.

Thanks to [Tamim Shahriar Subeen](https://medium.com/@subeen) Vaiya :) .

Keep

Too Long; Didn't Read

Build an AI-based text classifier with Tensorflow & NoSQL

Divide and Conquer (Merge Sort)

Too Long; Didn't Read

Company Mentioned

@promilaghoshmonty

RELATED STORIES