Related tags:
sortingrecursiondivide-and-conquermicrosoft-interview-questionsamazon-interview-questionscoding-interview-questionsDifficulty: Medium, Asked-in: Microsoft, Amazon, Goldman Sachs, Qualcomm, Bloomberg, Paytm
Merge sort is a popular sorting algorithm that uses 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 sorting problem of size n using solution of smaller sub-problems or by applying divide and conquer strategy? Let's think!
If we observe the above diagram, divide and conquer idea looks like this:
Divide part: Divide 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: We solve sub-problems recursively and sort both smaller halves. We need not worry about solution to the sub-problems because recursion will do this work for us. Think!
Combine part: We merge both sorted halves to generate the final sorted array. In other words, we combine solution of both the sub-problems of size n/2 to solve sorting problems of size n. How? Think!
Suppose function mergeSort(int A[], int l, int r) sorts entire array A[] with left and right ends 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 solution of the larger problem, i.e., merging both sorted halves to create the larger sorted array. How can we do it? Let's think!
If we store 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 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 X[] and Y[] from the start. We compare elements in both 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 to build partially sorted array A[]. 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 two extra arrays of size equal to the size of left and right sorted parts i.e. size of left sorted part = mid - l + 1, size of right sorted part = r - mid. Note: 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 two-pointer approach of problem-solving where we build partial solution by moving pointers 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 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 loop due to condition j = n2, then we have reached the end of array Y[] and entirely placed all values of Y[] in A[]. But there may be some values remaining in X[] that still need to be put in the larger array A[]. The idea is: These values are greater than all values available in A[], so we copy 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 loop due to condition i = n1, then we have reached the end of array X[] and entirely placed all 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 values available in A[], so we copy 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 iterative algorithm. To understand this better, let's visualize time complexity of each critical step and do the sum to calculate overall time complexity.
If we observe closely, merging algorithm time complexity depends on the time complexity of merging loop where comparison, assignment, and increment are critical operations. There could be two different perspectives to understanding 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 n > 1 (merge sort on single element takes constant time), we can break down the time complexities as follows:
For calculating T(n), we need to add 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: The merge sort function works correctly when number of elements is not even. To simplify the analysis, we assume that n is a power of 2. This assumption does not affect order of growth in the analysis. Think!
Time complexity analysis of merge sort using Recursion Tree Method
In this method, we draw recursion tree and count the total number of operations at each level. Finally, we find overall time complexity by doing the sum of operations count at each level.
Time complexity analysis of merge sort using the Master Theorem
Master method is a direct way to get the solution for recurrences that can be transformed to the type T(n) = aT(n/b) + O(n^k), where a ≥ 1 and b > 1. There are following three cases of the analysis using master theorem:
Let's compare with merge sort recurrence
Here a = 2, b = 2 (a > 1 and b > 1)
It means, merge sort recurrence satisfy the 2nd case of master theorem. 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: The size of recursion call stack = Height of merge sort recursion tree = O(logn) (Think!).
Important note: We recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all test cases. Enjoy programming!
Content reference: Algorithms by CLRS
Please write in the message below if you find anything incorrect, or you want to share more insight. Enjoy learning, Enjoy algorithms!
Given a 2-dimensional matrix, print the elements in spiral order. We can imagine the spiral traversal as an ordered set of matrix segments with horizontal and vertical boundaries, where both boundaries are reduced by one at each step. This is a good matrix problem to learn problem-solving using iteration and recursion.
These are some critical reasons to study sorting algorithms: 1) It can help us to learn analysis of algorithms and various problem-solving approaches 2) Sorting can work as a problem-solving approach to solve several coding problems 3) We can learn code optimization techniques and variations in boundary conditions using sorting.
Given an integer array X[] of size n, write a program to find all the leaders in the array X[]. An element is a leader if it is strictly greater than all the elements to its right side. So the largest and last element of an array is a leader by default. This is an excellent problem to learn problem-solving using a single loop and variables.
Learning analysis of recursion is critical to understand the time complexity analysis of recursive algorithms. We will discuss these concepts related to the recursion analysis: Recurrence relations of recursive algorithms, steps to analyze the time complexity of recursion, Recursion tree method, and master theorem to analyze divide and conquer algorithms.
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.