Difficulty: Medium, Asked-in: Microsoft, Amazon, Goldman Sachs, Qualcomm, Bloomberg, Paytm
Merge sort is a popular sorting algorithm that uses a divide and conquer approach to sort an array (or list) of integers (or characters or strings). Here are some excellent reasons to learn this algorithm:
Suppose we need to sort an array A[l…r] of n integers starting from index l and ending at index r. The critical question is: can we solve the sorting problem of size n using the solution of smaller sub-problems or by applying the divide and conquer strategy? Let's think!
If we observe the above diagram, the divide and conquer idea looks like this:
Divide Part: divide the sorting problem of size n into two different and equal sub-problems of size n/2. We can easily divide the problem by calculating the mid.
Conquer Part: Now, we solve both sub-problems recursively and sort both the smaller halves. We need not worry about the solutions to the sub-problems because recursion will do this work for us. Think!
Combine Part: we merge both the sorted halves to generate the final sorted array. In other words, we combine the solutions of both the sub-problems of size n/2 to solve the sorting problems of size n. How? Think!
Suppose the function mergeSort(int A[], int l, int r) sort the entire array A[] with left and right end as input parameters.
Note: why are we not calculating mid using the formula (l + r)/2? Explore this excellent google blog to get an answer. Think!
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)
}
Solution Idea: Two Pointers Approach
After the conquer step, both left part A[l…mid] and right part A[mid+1…r] will be sorted. Now we need to combine the solution of both smaller sub-problems to build the solution of the larger problem, i.e., merging both sorted halves to create a larger sorted array. How can we do it? Let's think!
If we store the values of both sorted halves of A[] into two extra arrays of size n/2 (X[] and Y[]), then we can transform the problem into merging sorted arrays X[] and Y[] to the larger sorted array A[]. Using the sorted order property and comparing the values one by one, we can build the larger array sorted A[]. How do we implement it? Let's think!
We can use two separate pointers i and j to traverse the array X[] and Y[] from the start. We compare elements in both the arrays one by one and place a smaller value on array A[]. Another way of thinking would be: after each comparison, we add one element to the sorted output and build the partially sorted array A[]. Think! But one critical question is: can we merge these two sorted parts in place? Try to do some swapping and comparison operations to get the insight. Think!
Merging Algorithm Implementation Steps
Step 1: Memory allocation and data copy process
We allocate the two extra arrays of size equal to the size of the left and right sorted parts i.e. size of left sorted part = mid - l +1, size of right sorted part = r - mid. Note: here we include value at mid-index in the left part.
int n1 = mid - l + 1
int n2 = r - mid
int X[n1], Y[n2]
Finally, we copy the left and right sorted parts of A[] into both extra arrays.
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: Now we start the merging process using two pointers loop.
Note: This is a two-pointer approach of problem-solving where we build the partial solution by moving pointer i and j in the same direction.
int i = 0, j = 0, k = l
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
Loop will stop when any one of the two pointers reaches the end of its array (either i = n1 or j = n2). At this stage, there will be two cases of boundary conditions:
Boundary Condition 1: If we exit the loop due to condition j = n2, then we have reached the end of the array Y[] and entirely placed all the values of Y[] in A[]. But there may be some values remaining in X[] which still need to be put in the larger array A[]. The idea is: these values are greater than all the values available in A[], so we copy the remaining values of X[] in the larger array A[]. Think!
while (i < n1)
{
A[k] = X[i]
i = i + 1
k = k + 1
}
Boundary Condition 2: If we exit the loop due to condition i = n1, then we have reached the end of the array X[] and entirely placed all the values of X[] in A[]. But there may be some values remaining in Y[] which still need to be put in the larger array A[]. The idea is: these values are greater than all the values available in A[], so we copy the remaining values of Y[] in the larger array A[]. Think!
while (j < n2)
{
A[k] = Y[j]
j = j + 1
k = k + 1
}
Merging Algorithm Pseudocode
void merge(int A[], int l, int mid, int r)
{
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 i = 0, j = 0, k = l
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)
{
A[k] = X[i]
i = i + 1
k = k + 1
}
while (j < n2)
{
A[k] = Y[j]
j = j + 1
k = k + 1
}
}
Time and Space Complexity Analysis of the Merging Algorithm
This is an excellent code to understand the analysis of an iterative algorithm. To understand this better, let's visualize the time complexity of each critical step and do the sum to calculate the overall time complexity.
If we observe closely, then the merging algorithm time complexity depends on the time complexity of the merging loop where comparison, assignment, and increment are the critical operations. There could be two different perspectives to understand this analysis:
Space complexity = extra space for storing the left part + extra space for storing the right part = O(n1) + O(n2) = O(n1 + n2) = O(n)
Let's assume that T(n) is the worst-case time complexity of merge sort for n integers. When we n >1 (merge sort on a single element takes constant time), then we can break down the time complexities as follows:
For calculating the T(n), we need to add the time complexities of the divide, conquer, and combine part => T(n) = O(1) + 2T(n/2) + O(n) = 2T(n/2) + O(n) = 2T(n/2) + cn
Note: Merge sort function works correctly when the number of elements is not even. But to simplify the analysis, we assume that n is a power of 2 where the divide step creates the sub-problems of size exactly n/2. This assumption does not affect the order of growth of the analysis. Think!
Analysis of Merge Sort using the Recursion Tree Method
In this method, we draw a recursion tree and count the total number of operations at every level. Finally, we find the overall time complexity by doing the sum of operations count at each level.
Analysis of Merge Sort using the Master Theorem
Master method is a direct way to get the solution for the recurrences that can be transformed to the type T(n) = aT(n/b) + O(n^k), where a ≥ 1 and b > 1. There are the following three cases of the analysis using master theorem:
Let's compare with the merge sort recurrence
Here a = 2, b = 2 (a > 1 and b > 1)
It means, merge sort recurrence satisfy the 2nd case of the master theorem. So time complexity T(n) = O(n^k * logn) = O(n^1 * logn) = O(nlogn)
Space complexity of merge sort = space complexity of the merging process + size of recursion call stack = O(n) + O(logn) = O(n). Note: size of recursion call stack = height of the merge sort recursion tree = O(logn) (Think!)
Content Reference: Algorithms by CLRS
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get well-designed content on data structures and algorithms, machine learning, system design, oops, and mathematics. enjoy learning!
Given an array X[] of n integer elements, write a program to find the length of the longest subarray with a sum equal to 0. In general, for all j > i, find **max (j - i + 1)** among all subarray with zero-sum. Note: the length of a subarray starting from index i and ending at index j = j - i + 1.
EnjoyAlgorithms
Given an array X[] of n integers, return true if and only if it is a valid mountain array. The array X[] is a mountain array if and only if n >= 3 and there exists some i with 0 < i < n - 1 such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n - 1]. In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.
EnjoyAlgorithms