# Merge Sort

## Introduction

Can sorting be made faster? We have seen sorting techniques like (Insertion Sort, Selection Sort and Shell Sort) which have a quadratic running time. With growing size of the inputs, it becomes tough to use these algorithms. Is there any faster alternative? We would like to find answers to these questions in the Merge Sort article.

On the other hand if you are interested in watching a video for this article, you can subscribe our Youtube Channel.

## Purpose of the Article

In this article we try to answer the questions mentioned above. Yes there are many faster alternatives. And these are the ones which are widely used. A different class of algorithms, we also term them as Divide and Conquer algorithms. In most of the cases they have less than quadratic, mostly NlogN running time. In this article we will understand one such algorithm known as Merge Sort.

## A word about Divide and Conquer algorithms

The basic idea involves only three steps as mentioned below:

• Divide – the input into sub-problems.
• Conquer – the smaller sub-problems (mostly using recursion).
• Combine – the individual results of all the sub-problems to get the final result.

## Merge Sort – A faster sorting technique

At first this algorithm may seem to be a tough one, but if we can spend some time to understand the steps involved in its implementation and working, we might get it in the first go. To start with lets assume an array A containing N elements and we will sort it using merge sort. The steps are mentioned below:

Step 1: If the length of the input i.e. N is equal to one, return the input, because if there is one element it is already sorted.
Step 2: If the length of the input i.e. N is greater than one, we divide the array in two parts A[0, N/2] and A(N/2 +1, N) and recursively sort the two parts.
Step 3: Merge the two sorted sub-lists.

## Explanation and Approach

Suppose we have the below input to sort.

Clearly N is equal to 8, hence according to step 2 we divide the array into the below two sub-arrays:

Now recursing on both the sub-arrays individually, we again divide them further

Again recursing on all the four sub arrays

Now, if we analyze the above 8 sub arrays, each of them contain just one element and now according to Step 1 mentioned above, all of them are individually sorted. This precisely means that now we just have to merge all the sorted sub-arrays.

When we merge 6 and 10 the result would be a sub-array : 6 and 10
Similarly merging 13 and 5 would result in a sub-array : 5 and 13

So after the first level of merging we get four sorted sub-arrays as mentioned below:

Now we merge the sorted sub-arrays 1 with 2 and sub-arrays 3 with 4 separately
The results would be two new sub-arrays as mentioned below:

Now we are left with two sorted sub-arrays and we need to merge them. The result would be as below:

Result :

And we are done …

You must have noticed, that the major part of the algorithm is merging. So we write a merge routine first, our merge routine will take two sorted arrays and will merge them into a single sorted array and return the array. Below is the code for Merge subroutine.

Now the Merge-Sort routine is also very simple, it just divides the array into two parts and recursively calls itself, so that it can divide the array till there is one element left in each of the sub-arrays. After that it calls the merge routine passing the two sub-arrays. After completing execution it returns the final sorted array.

Below is the code for the Merge-Sort routine:

This is all about merge sort code. Let us analyze the running time of the Merge Sort algorithm.

## Analysis

We will analyze the merge routine and mergeSort routine one by one :

## Merge Routine

The merge routine basically traverse through the complete array once. So the running time is basically linear (i.e. traversing the array once). That means the running time for merge is directly proportional to N, that also makes sense. If we want to merge two lists, it would be good only if we visit each element once.

## Merge Sort Routine.

This routine does a constant amount of work to find the mid element. It takes time proportional to the length of the input to divide the array into two parts, which is again proportional to N.

This whole thing is repeated and it is done through recursion so we will try to write a recurrence equation for the same.

Let us say that T(N) is the time taken by the algorithm to complete the sorting. Hence T(N) will be equal to the sum of time taken to merge sort both the halves and the the time taken to merge the sorted halves.
T(N) = time taken to merge sort the left sub-array + time taken to merge sort the right sub-array + time taken to merge the results. That implies:
T(N) = T(N/2) + T(N/2) + θ(N) where θ(N) is for merging. Hence this is the recurrence equation for the algorithm.
T(N) = 2T(N/2) + θ(N)

This finally results into θ(NlogN) running time. To understand how, we need to see the recurrence tree for this recurrence.

A simple mathematics can deduce that the height of the recurrence tree is logN . And each level will add up to CN, hence the total time taken is CNlogN or we can say Θ(NlogN).

## Conclusion

We learnt that the Merge sort is relativey better way of sorting and performs better than Insertion Sort, Selection SOrt, Shell Sort etc in most of the cases.

To know more about Merge Sort, please visit the Wiki
Stay connected and stay Subscribed