Sorting the things in a proper and efficient manner is very important and it is the part of the everyone’s life. We came to many situation where we need to sort the things which will make the task easy. So, let’s learn something about sorting.

There are many types of sorting algorithms

1. Bubble Sort

2. Insertion Sort

3. Merge Sort

4. Count Sort

5. Shell Sort

6. Quick Sort

And there are many more but these are the important ones to understand. So, I will discuss about the Merge Sort in this blog.

Merge Sort Algorithm

Merge Sort are of many types like 2 way Merge Sort , 3 way Merge Sort, like this n way Merge Sort and Merge Sort using Divide and Conquer rule. In this blog, I will discuss Merge sort using Divide and conquer rule.

Merge Sort consider as a one the best sorting algorithm. It uses the concept of Divide and Conquer rule. it also use the recursive function concept and also take less time in comparison to other sorting techniques.

Merge sort is also effective on a large set of elements. Whereas other sorting techniques usually take too much time to sort large set of elements.

As merge sort follow the Divide and conquer rule. So let’s understand WHAT IS DIVIDE AND CONQUER RULE ?

Divide and Conquer

As the name suggest first you have to divide then you have to conquer the problems.

Suppose you are given with a big problem and if you try to solve this problem it will become difficult and also take time to solve it. So, to make it simpler you can divide this big problem into smaller and smaller problem like sub problems. Then you solve the smaller problems. After finding the solution of sub-problems you can combine their solution so that it will become easier to solve the solution of the bigger original problem. Using this approach it will become easier to solve any big problem.

Let’s understand this concept with the real life example

Before the independence of India, there was a rule of Britisher. Basically when they came to India to rule over it, it became very difficult to rule because people of different religions in India lived with the unity. So, Britishers use the concept of Divide and Rule. They start dividing the people against each other on the basis of religion, cast etc. and it became easy for them to rule over India.

Now let’s understand the Divide and conquer rule on sorting i.e. Merge sort

Suppose you are given with very large unsorted array containing n elements. If you use other sorting techniques it will take too much time. But using the concept of Divide and Conquer, you can divide the unsorted array into n subarray. And you will divide this array until one element is left. Then from the bottom you start sorting this sub array and side by side we merge it also. By merging all the sub arrays, we are going to get a new sorted array in a very less time as compared to other sorting techniques.

So basically we need to understand only three steps:-

1. First we divide the big problem into many smaller problems

2. Then we will find the solution of their smaller problems.

3. After finding the solution, then merge the solutions to find the solution of the original problem.

How Merge Sort Works?

As we know that using divide and conquer, we can break any big problem into smaller ones then we can find the solution of this problem.

Let’s understand Merge Sort Algorithm with the help of an example:

Suppose a array on integer is given containing 7 numbers { 5, 7, 1, 9, 3, 2, 4 }.

1. First, we will divide this array into two part by finding the mid value i.e. 9. So, we get two sub array {5,7,1,9} and {3,2,4}

2. Then we divide the left sub array {5,7,1} from the mid. So, we get two more sub array {5,7} and {1,9}. Then we again divide the {5,7} into two sub array {5} and {7} and {1,9} into {1} and {9}

3. Similarly, we divide the right sub array {3,2,4} from the mid. So, we get two more sub array {3,2} and {4}. Then we again divide the {3,2} into two sub array {3} and {2}.

4. Now, we divided the array into many sub array and now it cannot be divided further. So, our next step will be start sorting from the bottom and side by side start merging them from the bottom.

5. If we see left hand side, we will sort 5 and 7 merge them in their above array that is going to be {5,7} and similarly sort 1 and 9 and merge them {1,9}. Now at this level again we sort the sub array {5,7} and {1,9} and merge them. So our final left subarray will be {1,5,7,9}.

6. If we see right hand side, we will sort 3 and 2 merge them in their above array that is going to be {2,3}. Now at this level again we sort the sub array {2,3} and {4} and merge them. So our final right subarray will be {2,3,4}.

7. Now we are left with the only two sub array that is {1,5,7,9} and {2,3,4}. We will sort them and merge them into the original array. So finally our sorted array be like {1,2,3,4,5,7,9}.

Pseudocode of Merge Sort

Merge_Sort( arr[], l , r){

If( r > l ){

First find middle element of the array to divide it into equal half.

Mid = l + (r-l)/2;

Then call Merge_Sort function for the first half

Merge_Sort(arr, l ,Mid);

Then call Merge_Sort function for the Second half

Merge_Sort(arr, Mid+1, r);

At last merge the two half by calling merge function;

merge(arr , l , Mid, r);

}

}

Merge Sort program in c++

Complexity Analysis of Merge Sort

Now let’s discuss the time and space complexity of the merge sort. Merge sort is a stable sorting means same elements order in an array have the same positions with respect to each other. For the time complexity we will find the time taken by merge sort in three different cases :-

1. Best Case — O(nlogn)

2. Average Case — O(nlogn)

3. Worst Case — O(nlogn)

Here in all the cases time complexity would be O(nlogn). That’s why it is the best sorting algorithm in comparison to other sorting algorithms.

And Space complexity is O(n).

I hope this article is very helpful for the understanding of Merge Sort.