Divide and Conquer (Merge Sort)

1_z0fUKBPH_qyPQX6F3wuDPQ.png

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 conqueror 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.

1_Sqgt6rGJ9qwwvZxNxr7cAw

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:

1_1XkvF-qR1eGstxuwp_12fw

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(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 🙂 .

You can find this article from Hacker Noon 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s