Table of Contents

## Introduction

Sorting in programming refers to placing the elements of a data structure in a specific and meaningful manner. Sorting is an essential part of data processing. Efficient sorting algorithms are crucial so that we can perform operations that require sorted input optimally.

Whenever we search for something on Amazon or Flipkart, the search result is sorted based on filters like relevance, price, and rating. These companies deal with enormous data sets, so it becomes crucial to use a sorting algorithm that can provide results lightning-fast and provide users with a hassle-free experience.

Due to its importance in system design, questions on sorting algorithms are prevalent in technical interviews of companies like Google, Amazon, Microsoft, and Facebook.

It is vital to know how these sorting algorithms work internally. Having in-depth knowledge of sorting algorithms will help you to become a great software developer.

Merge sort is one of the most efficient sorting algorithms. Today in this article, we will discuss the merge sort algorithm with its implementation. But before diving into the concepts of merge sort, let’s understand the basics first.

Did you know? Merge sort is frequently asked question in Infosys Certification Exam (InfyTQ) 2021

## What is merge sort?

Merge sort is a divide and conquer algorithm. It divides the array repeatedly into smaller subarrays until each subarray contains a single element and merges back these subarrays in such a manner that results in a sorted array.

Now the question is, why does it even work? What is its fundamental working principle of merge sort?

The fundamental working principle of merge sort is that an array of size one is always sorted! Meaning, if we consider that we are having only a single element in the array, then the array is sorted, and while merging back, the idea is to merge two subarrays that are sorted. So at the core, this problem is broken down into merging two sorted arrays into a third one which is a famous and a standard question!

## Algorithm

Merge sort is easy to implement, but you should have a sound knowledge of recursion. Recursion is very important to implement the merge sort. As mentioned earlier in the definition, the merge sort has two main parts: the first is to break down the array into smaller parts, effectively called smaller subarrays.

The second one is to merge the subarrays, assumed to be sorted(we know the assumption is true as The Principle of Mathematical Induction, **PMI** comes to rescue. Read the blog on Recursion and Backtracking Algorithm With Practice Problem to learn more) to get the final sorted array.

So we will create two functions. The first function will recursively divide the array into smaller subarrays, and another function will merge it back, effectively merging the two sorted arrays.

The algorithm of merge sort is as follows.

```
mergeSort(arr, size)
If size > 1
Step 1: Find the size of the leftSubArray and rightSubArray so that we can divide the array into two-part
leftSize = size / 2;
rightSize = size - leftSize;
Step 2: Call the mergesort for the leftSubArray
mergeSort(leftSubArray, leftSize);
Step 3: Call the mergesort for the rightSubArray
mergeSort(rightSubArray, rightSize);
Step 4: Call the merge function to merge these two halves mergeTwoSortedArray(leftSubArray, rightSubArray, arr,
leftSize, rightSize)
```

## Implementation In C++

Below is the implementation of the merge sort algorithm in C++.

```
#include <iostream>
using namespace std;
// Function to merge left and right subarrays of arr.
void mergeTwoSortedArray(int leftSubArray[], int rightSubArray[], int arr[], int n, int m)
{
// i is for leftSubArray, j is for rightSubArray, k is for arr
int i = 0;
int j = 0;
int k = 0;
while (i < n && j < m) {
if (leftSubArray[i] <= rightSubArray[j]) {
arr[k] = leftSubArray[i];
i++;
}
else {
arr[k] = rightSubArray[j];
j++;
}
k++;
}
// copy remaining elements of leftSubArray[]
while (i < n) {
arr[k] = leftSubArray[i];
i++;
k++;
}
// copy remaining elements of rightSubArray
while (j < m) {
arr[k] = rightSubArray[j];
j++;
k++;
}
}
void mergeSort(int arr[], int size){
//this is a special case - it means we don't have an array to sort. Mind that the array size can never be less than 0
if (size == 0) {
return;
}
// if only one element is present in arr then we don't need to divide array further as one element is sorted in itself.
if(size == 1)
{
return;
}
// create leftSubArray and rightSubArray - and copy the elements as it is from arr.
int n = size / 2;
int m = size - n;
int leftSubArray[n];
int rightSubArray[m];
//pointer for arr
int k = 0;
for(int i = 0; i < n; i++)
{
leftSubArray[i] = arr[k];
k++;
}
for(int j = 0; j < m; j++)
{
rightSubArray[j] = arr[k];
k++;
}
//call mergeSort on left subarray
mergeSort(leftSubArray, n);
//call mergeSort on right subarray
mergeSort(rightSubArray, m);
//merging the two sorted subarrays back to the original one
mergeTwoSortedArray(leftSubArray, rightSubArray, arr, n, m);
return;
}
int main()
{
int arr[] = { 14, 17, 22, 4, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr,n);
cout<<"Sorted array: ";
for(int i = 0; i < n; i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
Output:
Sorted array: 1 4 5 14 17 22
```

**Time Complexity**

The recurrence relation for merge sort algorithm can be written as :

**T(n) = 2T(n / 2) + θ(n) **

This recurrence relation can be solved by the recurrence tree or master theorem. The recurrence tree for the above relation can be drawn as:

Image Source: researchgate.net

We are dividing the array into two parts at each step till each subarray contains only one element, so the number of levels in this tree would be log_{2}n, and at these different levels, while merging back the array, we will at max compare *n *elements. So the time complexity of the merge sort is **θ(n*log**_{2}**n).**

The time complexity of Merge Sort in worst, average, and best case is **θ(n*****log**_{2}**n****)** as merge sort always divides the array into two halves regardless of the fact that what is the present state of the array and takes linear time to merge the array.

**Space complexity**: The space complexity of the above code is O(n) as we are using an auxiliary array to copy the left and right subarray. But if you are asked by the interviewer to consider the stack memory then we are having a maximum of *log*_{2}*n *function calls waiting in the stack which yields an extra space complexity of O(log_{2}n). So total space complexity becomes O(n+log_{2}n) as n is greater than log_{2}n, we ignore the log_{2}n part.

There is another space-optimised approach to implement the merge sort called in-place merge sort in which instead of copying an array in left and right subarray we divide an array with help of pointers logically creating division in the original array by specifying the window for every recursive call. We shift the elements of the array to finally achieve the sorted configuration.

Thus taking no extra space and having O(1) space complexity. But if you are asked by the interviewer to consider the stack memory then we have* log _{2}n* function calls waiting in the stack memory and hence leads to O(log

_{2}n) space complexity.

We have discussed all the technicalities of merge sort and also implemented it. You should try to implement the merge sort on CodeStudio.

CodeStudio is a platform developed by some aspiring enthusiasts and working professionals who have experience in companies like Google, Amazon, Microsoft. At CodeStudio you get interview problems, interview experiences, and practice problems that can help you to land your dream job.

## Applications of merge sort

There are plenty of applications of merge sort. Some of the applications of merge sort are listed below.

- Merge sort is helpful to sort a linked list in O(N logN) time.
- Merge sort is useful for counting inversion in a list or array.
- Merge sort is useful for external sorting. Which is useful when the result does not fit in memory.

## Drawbacks of Merge Sort

Drawbacks of the merge sort are as follows:

- Merge sort is not efficient for sorting input of large size if you are having low stack space.
- Merge sort while sorting the array goes through the entire process even if the array is sorted.
- Merge sort takes an extra space of O(n) in standard(Outplace) implementation.

## Frequently Asked Questions

**What is a merge sort algorithm with an example?**

Merge sort is a divide and conquer algorithm. It divides the array repeatedly into smaller subarrays until each subarray contains a single element and merges back these subarrays in such a manner that results in a sorted array. Ex: sorting the students’ details on the basis of their marks.

**How does merge sort algorithm work?**

Merge sort algorithm is a divide and conquer algorithm it divides the array into smaller subarray until each subarray contains only a single element and an array of size one is always sorted using this property it merges two sorted subarrays to a single subarray.

**Why merge sort is Outplace?**

The standard implementation of merge sort is outplace as it requires an extra space of O(n) for temporary arrays.

**Is merge sort in place sort?**

No, the standard approach is not in-place, but we can optimise the merge sort to work in-place.

**Does merge sort require extra space?**

Yes, merge sort requires O(n) extra space for temporary arrays in outplace implementation and no extra space for in-place implementation(if the stack space is not considered).

## Key Takeaways

In this article, we discussed the merge sort with all crucial aspects that are necessary to implement the merge sort. We discussed the merge sort algorithm in detail and implemented the merge sort in c++. We also took a look at the time and space complexity of merge sort in detail. In the end, we also discussed the applications and drawbacks of the merge sort algorithm.

**By Pranchal Agrahari**

## Leave a Reply