November 17, 2022
Merge Sort Algorithm
Difficulty: Medium, Asked-in: Microsoft, Amazon, Goldman Sachs, Qualcomm, Bloomberg, Paytm

By Shubham Gautam
7 min read
Why merge sort?
Merge sort uses a divide-and-conquer idea to sort input elements into increasing order. Here are some critical reasons to learn this algorithm:
- Merge sort is an efficient sorting algorithm that works in O(nlogn) time complexity (both best and worst cases).
- This is an efficient algorithm for sorting linked lists in O(nlogn) time.
- Merge sort is an excellent algorithm for learning the concept of recursion and analysis of recursive code. We can use a similar approach to solve other coding questions.
- The merging procedure of merge sort is based on the two-pointers approach, where both pointers move in the same direction. We can use a similar method to solve other coding problems.
Merge sort idea
Suppose we need to sort an array A[ ] of n integers in increasing order. Now the critical question would be: How can we solve the sorting problem using smaller sub-problems by applying the divide and conquer approach? Let's think!
If we observe from the above visualization, divide and conquer idea of merge sort will go like this:
Divide: We divide the problem of size n into two equal sub-problems of size n/2 by calculating the mid-index.
- Subproblem 1: Sorting array A[] from l to mid.
- Subproblem 2: Sorting array A[] from mid + 1 to r.
Conquer: Now, we sort both halves recursively by calling the same merge sort method for different input parameters.
Combine: We merge both sorted halves to the final sorted array.
Merge sort steps
Suppose mergeSort(A[], l, r) sort A[] where left index l and right index r are input parameters.
Divide: We calculate mid index, mid = l + (r — l)/2
Conquer:
- We call the same merge sort function with l as the left index and mid as the right index to sort the left half, i.e., mergeSort(A, l, mid).
- We again call the same merge sort function with mid + 1 as the left index and r as the right index to sort the right half, i.e., mergeSort(A, mid + 1, r).
Combine: Now, using another function merge(A, l, mid, r) inside the mergeSort(), we merge both smaller sorted parts into a larger sorted array.
Base case: The sub-array of size 1 is the smallest sorting problem, which is already sorted. So when l >= r during the recursion, we return.
Merge sort pseudocode
void mergeSort(int A[], int l, int r)
{
if(l >= r)
return
int mid = l + (r - l)/2
mergeSort(A, l, mid)
mergeSort(A, mid + 1, r)
merge(A, l, mid, r)
}void mergeSort(int A[], int l, int r)
{
if(l >= r)
return
int mid = l + (r - l)/2
mergeSort(A, l, mid)
mergeSort(A, mid + 1, r)
merge(A, l, mid, r)
}Merge sort visualisation
Implementation of merging process
After the completion of conquer step, both left part and right part will be sorted. Now we need to merge both sorted halves to create a larger sorted array. How can we do it? Let's think.
If we copy both sorted halves into two extra arrays (X[] and Y[]), we can convert this problem into merging sorted arrays X[] and Y[] to the larger sorted array A[]. Now we can incrementally build the larger array sorted by comparing values one by one in X[] and Y[].
For this, we can use two pointers i and j to compare elements in both smaller arrays. When we find X[i] < Y[j], we place X[i] on A[] and increment pointer i. Otherwise, we place Y[j] on A[] and increment pointer j. In simple words: After each comparison, we add one value to the sorted output and incrementally build the sorted array A[]. Think!
Here are the steps of merging algorithm
Step 1: We allocate two extra arrays (X[] and Y[]) and copy elements of left and right sorted parts of A[] in both arrays.
int n1 = mid - l + 1
int n2 = r - mid
int X[n1], Y[n2]
for (int i = 0; i < n1; i = i + 1)
X[i] = A[l + i]
for (int j = 0; j < n2; j = j + 1)
Y[j] = A[mid + 1 + j]int n1 = mid - l + 1
int n2 = r - mid
int X[n1], Y[n2]
for (int i = 0; i < n1; i = i + 1)
X[i] = A[l + i]
for (int j = 0; j < n2; j = j + 1)
Y[j] = A[mid + 1 + j]Step 2: Merging algorithm loop
We initialise three pointers i = 0, j = 0, and k = l for traversing X[], Y[], and A[]. Now we run a loop until any smaller arrays reach their end. In the first step, we compare X[0] and Y[0] and place smaller element at A[0]. We also increment pointer k and pointer in the smaller array containing the smaller value.
Similarly, we move forward by comparing X[i] and Y[j]. We put a smaller value at A[k], increment k by one and increment pointers i or j based on the comparison X[i] < Y[j] or X[i] > Y[j].
while (i < n1 && j < n2)
{
if (X[i] <= Y[j])
{
A[k] = X[i]
i = i + 1
}
else
{
A[k] = Y[j]
j = j + 1
}
k = k + 1
}while (i < n1 && j < n2)
{
if (X[i] <= Y[j])
{
A[k] = X[i]
i = i + 1
}
else
{
A[k] = Y[j]
j = j + 1
}
k = k + 1
}Step 3: Loop termination and boundary conditions
We stop the loop when i = n1 or j = n2.
Boundary condition 1: If we reach end of the array Y[] due to condition j = n2, there can be some values still remaining in X[]. So we copy remaining values of X[] at the end of array A[].
while (i < n1)
{
A[k] = X[i]
i = i + 1
k = k + 1
}while (i < n1)
{
A[k] = X[i]
i = i + 1
k = k + 1
}Boundary condition 1: If we reach end of the array X[] due to condition i = n1, there can be some values still remaining in Y[]. So we copy remaining values of Y[] at the end of array A[].
while (j < n2)
{
A[k] = Y[j]
j = j + 1
k = k + 1
}while (j < n2)
{
A[k] = Y[j]
j = j + 1
k = k + 1
}Merging algorithm pseudocode
Analysis of merging process
Merging process time complexity depends on the two pointers while loop where comparison, assignment, and increment are the critical operations. Let's understand the analysis from two different views:
- Viewpoint 1: At each iteration step, we perform one comparison and increment pointer i or j. In other words, we are traversing both smaller arrays until the end.
- Viewpoint 1: We place one element from the smaller array to the larger array A[] at each iteration step.
So we are doing constant operations for each element. So overall time complexity = n * O(1) = O(n). Space complexity = Space complexity for storing two extra arrays = O(n1) + O(n2) = O(n1 + n2) = O(n)
Time and space complexity of merge sort
Suppose T(n) is the merge sort time complexity for n elements. When n > 1, we can break down the time complexities of each step as follows:
- Divide: We are calculating mid index in constant time. So time complexity of divide part is O(1).
- Conquer: We are recursively sorting two smaller halves of size n/2, where each sorted half will take T(n/2) time. So 2*T(n/2) will be the overall time complexity of the conquer part.
- Combine: This is equal to the time complexity of the merging process, which is O(n).
Finally, we add time complexities of the divide, conquer, and combine parts to get the final recurrence relation of merge sort to calculate time complexity T(n) => T(n) = O(1) + 2 T(n/2) + O(n) = 2 T(n/2) + O(n) = 2 T(n/2) + cn
- T (n) = c, if n = 1
- T(n) = 2 T(n/2) + cn, if n > 1
Merge sort time complexity analysis using recursion tree method
The idea here is to draw recursion tree of merge sort recurrence, count the total cost of operations at each level and add them level by level to find the overall time complexity.
Merge sort time complexity analysis using the Master Theorem
This is one of the popular method to directly get the solution for divide and conquer recurrences in the form T(n) = aT(n/b) + f(n), where a ≥ 1 and b>1. There are three cases of master theorem:
- If f(n) = O(n^k) and k < logb(a): T(n) = O(n^logb(a))
- If f(n) = O(n^k) and k = logb(a): T(n) = O((n^k) * logn)
- If f(n) = O(n^k) and k > logb(a): T(n) = O(n^k)
Let's compare with the merge sort recurrence with master theorem recurrence:
- T(n) = 2 T(n/2) + cn, if n > 1
- T(n) = aT(n/b) + O(n^k)
Here a = 2, b = 2 (a > 1 and b > 1) => O(n^k)= cn = O(n¹) => k = 1
Similarly, logb(a) = log 2(2) = 1, Hence => k = logb(a) = 1
It means, Merge sort recurrence satisfy the 2nd case of the master theorem.Time complexity T(n) = O(n^k * logn) = O(n^1 * logn) = O(nlogn)
Merge sort space complexity = Space complexity of merging procedure + Space complexity of recursion call stack = O(n) + O(logn) = O(n). Note: The size of recursion call stack will be equal to the height of the recursion tree, which is O(logn). Think!
Critical ideas to think in merge sort
- Merge sort is a stable sorting algorithm.
- Due to the overhead of recursive calls and the merging process, merge sort works slower than insertion sort for small input sizes.
- Insertion works in O(n) time complexity for the almost sorted array or sorted array. But merge sort goes through the complete process and takes O(nlogn) time for the sorted or nearly sorted array.
- Merge sort is based on the divide and conquer idea, where every sub-problem is independent. So it can work efficiently in the parallel processing environment.
- We can iteratively implement merge sort without using an auxiliary stack. Think and explore.
Similar concepts and questions to explore
- Find inversion count of an array
- External sorting algorithm
- Quick sort algorithm
- Binary search algorithm
- Difference between recursion and iteration
- Recursive algorithm of the maximum sub-array sum
- Recursive algorithm of finding max and min in an array
- Recursive algorithm finding majority element
- Recursive algorithm finding max difference in array
- Iterative merge sort
For more content, explore our free DSA course and coding interview blogs.
If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!
Originally published at https://www.enjoyalgorithms.com/blog/merge-sort-algorithm/