 # Merge Sort Algorithm

We have already discussed the Bubble Sort Algorithm, and in this post, we are going to discuss another sorting algorithm MERGE SORT ALGORITHM.

As the name says this sorting algorithm might be related to merging some datasets.

And yes you guessed it right, Merge Sort Algorithm is a divide and conquer Algorithm, where we first break the datasets into some sub-datasets and then do some stuff on it and lastly we merge the sub-datasets.

Since this process involves merging the datasets, this Algorithm is called the Merge Sort Algorithm.

## Divide and Conquer

In computer Science, Divide and Conquer is a very powerful technique to solve real-life problems.

Divide and Conquer include three steps :

(i) Dividing the problem into subproblems.
(ii) Solving the subproblems.
(iii) Merging the solution of the subproblems to solve the actual problem.

Let us consider a real-life example, suppose you are only a warrior left in the battleground, and on another side, there are five other warriors who are your enemies.

Now how will you defeat them ??

It is impossible for you to defeat all five warriors in one go, instead, you can plan to beat them individually, so you decided to tackle one enemy at a time, and this way you defeat all the five enemies. This is the concept of divide and conquer.

Divide the problem into subproblems so that instead of tackling the whole problem in one go, tackle the subproblems.

Applications of Divide and Conquer are Binary Search, Merge Sort, Problems of Tree Data Structures, etc.

Divide and conquer Algorithm uses recursion to conquer a problem, click here to know more about recursion.

## Merge Sort

Hope Divide and Conquer Algorithm is clear to you.

Let us understand it more clearly by using an example,

We will discuss the Merge Sort Algorithm to understand Divide and Conquer Algo.

We already know what sorting is. So now let us consider an array to understand merge sort.

### 1st Step of the Algorithm

Divide the array into two halves.

We will keep it dividing until we get datasets of single element.

This is the first step of Merge Sort, dividing the array dataset individually.

Now let us discuss the code for implementing the first step of Merge Sort.

``````void merge_sort_First_step(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r-l)/2;

merge_sort_First_step(arr, l, m);
merge_sort_First_step(arr, m+1, r);
}
}``````

In the above code, we first find the middle element of the array, initially l=0 and r = n-1, and after that, we recursively divide the left subarray and then the right subarray with the same process until (l<r).

This recursion will divide the array into individual subarrays.

### 2nd Step of The Algorithm

Now let us move to our next step, currently, we have just individual elements of the array.

We will merge the individual datasets but instead of merging directly, we will merge it such that the elements of the merged dataset are sorted.

Let us understand it by the same example,

In this step we are actually conquering the datasets, at the same time we are merging the datasets as well.

This is the main logic of 2nd step of Merge Sort, as you can see after merging 4 and 1 we are getting a merged dataset with (1,4) as an element.

But the Question arises, how to merge two datasets to form a sorted dataset?

If you observe carefully, we are actually merging two sorted sub-datasets to form a sorted dataset.

Yes, you heard it right, we are actually merging two sorted sub-datasets to form a sorted dataset.

All unsorted dataset containing only a single element is also a sorted dataset.

In fact, this is a very famous interview Question, how to merge two sorted datasets into a sorted dataset.
Let us discuss this first.

## Merging two sorted arrays into a sorted array

Given two sorted arrays of size m and n respectively, we have to merge it to form a new sorted array of size (m+n).

Please try this problem by yourself, it is highly recommended to try it once.

Now let us discussed the solution of the above problem, the logic is very simple, we will run a while loop maintaining three variables (i, j, k) simultaneously.

Let’s see the code first,

``````void mergeSortedArrays(int x[], int y[], int n, int m, int z[])
{
int i = 0, j = 0, k = 0;

while(i < n && j < m)
{
if (x[i] < y[j]) {
z[k] = x[i];
i++;
}
else {
z[k] = y[j];
j++;
}
k++;
}

while(i < n) {
z[k] = x[i];
k++; i++;
}
while(j < m) {
z[k] = y[j];
k++; i++;
}
} ``````

Here we are maintaining three variables i, j, k simultaneously.

The idea is that since both arrays are sorted, we will compare the first element of the first array with the first element of the second array and we will accordingly fill the smaller element to the z[] array.

We will continue his process until we traverse either of the two arrays completely.

Let us understand it more clearly with an example,

This is how we will fill the z[ ] array . Hope this diagram makes your concept clear.

### Merging Step in Merge sort Algorithm

Now again come back to our main topic, we will merge the sub-arrays in the same fashion that we discussed.

Let us discuss the code of the 2nd step of the Merge Sort Algorithm.

``````void merge(int arr[], int l, int m, int r)
{
int left_size = m-l+1;
int right_size = r-m;

int *left = new int[left_size];
int *right = new int[right_size];

for(int i = l; i <= m; i++) {
left[i-l] = arr[i];
}

for(int i = m+1; i <= r; i++) {
right[i-m-1] = arr[i];
}

int i = 0;
int j = 0;
int k = l;

while(i < left_size && j < right_size)
{
if(left[i] < right[j]) {
arr[k] = left[i];
i++;
}
else {
arr[k] = right[j];
j++;
}
k++;
}

while(i < left_size)
{
arr[k] = left[i];
i++; k++;
}
}``````

I know code is a bit lengthy but don’t worry we will discuss each and every step very clearly.

Now take an example of merging two subarrays from the same example which we discussed earlier.

We will discuss the dash – marked dataset, we will discuss how we will merge it in this algorithm.

Step 1: For the dash marked area l = 4 , m = 5 and r = 6.
Step 2: Create two temporary arrays of size (m-l+1) and (r-m) respectively.

We created these two arrays for the reference so that with the help of it we can update our original array.

Step 3: Fill the temporary arrays with the value accordingly.
Step 4: Merge the two arrays and update the original array in the same manner that we discussed earlier.

That’s it. Hope I can able you to understand the 2nd step of the Merge Sort.

NOTE that here we have the original array with us initially and we also have a range of index within which we have to convert the dataset to sorted dataset.

So we will first create two sub-dataset and fill it data accordingly and then merge both of them to update the original array.

We follow the same way for all the sub-dataset and at last, we get our sorted array. This is the Masterstroke Logic of Merge Sort Algorithm.

### Analysis of Merge Sort Algorithm

Dividing the dataset to sub-datasets of two and then merging it again takes O(n*log(n)) complexity.

Best Case Time Complexity: O(n*log n)
Average Case Time Complexity: O(n*log n)
Worst Case Time Complexity: O(n*log n)

Even if it a sorted array, merge sort will follow these steps to find whether the array is sorted or not, so Best, Average, and Worst case complexities are the same.

### Complete Merge – Sort code in C/C++

``````#include<bits/stdc++.h>
using namespace std;

void merge(int arr[], int l, int m, int r)
{
int left_size = m-l+1;
int right_size = r-m;

int *left = new int[left_size];
int *right = new int[right_size];

for(int i = l; i <= m; i++) {
left[i-l] = arr[i];
}

for(int i = m+1; i <= r; i++) {
right[i-m-1] = arr[i];
}

int i = 0;
int j = 0;
int k = l;

while(i < left_size && j < right_size)
{
if(left[i] < right[j]) {
arr[k] = left[i];
i++;
}
else {
arr[k] = right[j];
j++;
}
k++;
}

while(i < left_size)
{
arr[k] = left[i];
i++; k++;
}
}
void merge_sort_First_step(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r-l)/2;

merge_sort_First_step(arr, l, m);
merge_sort_First_step(arr, m+1, r);
merge(arr,l,m,r);
}
}

int main()
{
int n;
scanf("%d",&n);

int arr[n];

for(int i=0;i<n;i++) {
scanf("%d",&arr[i]);
}

merge_sort_First_step(arr,0,n-1);

for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}``````

Hope Merge Sort is clear to you. Merge Sort is one of the best Sorting Algorithm along with Quick Sort. Merge Sort is used widely.

That’s all folks..!!![Wikipedia Reference] Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.