Interview Kickstart has enabled over 3500 engineers to uplevel.
Merge sort is one of the most efficient and popular sorting algorithms. If you are a software developer preparing for your next tech interview, then this one algorithm you must review.
Sorting algorithm questions are a big part of coding interviews at tech companies. In this article, we will help get one step closer to cracking that interview.
Merge sort is a general-purpose comparison-based sorting algorithm — which means that the algorithm compares the elements of the list to sort it.
Most implementations of this algorithm produce a stable sort, i.e.,, i.e., the order of any two equal elements in the sorted list and the original list stays the same.
Merge sort has a consistent speed for a given size of data. Therefore, it’s not preferred for sorting an almost sorted array. It works well for sorting linked lists.
Merge sort uses the concept of divide and conquer. The problem is divided into multiple subproblems, solved individually, and finally, the result of the subproblems are combined to form the final solution.
In the case of merge sort, at each step, we divide the list into two smaller sublists until the size of each list reduces to 1. The size of the two sublists is equal when the list is of even length. If the list length is odd, the size of the sublists differs by 1.
We then sort the sublists and merge them to produce the sorted list.
We may have used a similar technique in real life while sorting a huge number of boxes (or any object). When the number is large, it becomes difficult to sort everything in one go. It’s easier to divide the boxes into smaller chunks, sort those chunks, and then bring the sorted chunks together to get all the boxes in the sorted order.
We divide the list into smaller sublists and make a recursive call to sort the sublists. The recursive call made to sort the sublists divides the sublists into even smaller sublists.
This process continues until the size of the list reduces to 1.
At this step, we already have our sublists sorted. Now, all we need to do is merge them.
Merging of the lists happens from the bottom to the top. In the figure above, we can see that all the lists in the bottom-most row are of size 1 — these can be considered “sorted,” as they contain just one element.
Now, we need to sort the lists in the second row from the bottom, and for that, we will merge the already sorted 1-element lists. We first merge the sorted lists of size 1 to produce sorted lists of size 2, then merge the sorted lists of size 2 to create sorted lists of size 4, and so on.
We stop when we are left with a single list.
Let’s see how we can merge two sorted lists of arbitrary size. The idea is pretty simple and straightforward:
Have a look at the following figure to see this in action:
The merging will repeatedly occur until we get a single list of size n:
Now that we know how merge sort works, let’s put it in pseudocode. You can use this to create your code in any programming language you like.
We’ve used C++ to demonstrate the merge sort code. You don’t need to restrict yourself! Feel free to use this as a reference to code in C, Java, Python, or any programming language of your choice.
Array before sorting :
5 4 1 6 3 2 8 7
Array after sorting :
1 2 3 4 5 6 7 8
The time complexity of merge sort is O(n log(n)). This is how it’s calculated:
Let’s count the number of rows in the dividing step of the algorithm. We’ll call the number of rows “num_rows” and the size of the list “n”. We keep dividing the list until the size of the list reduces to 1.
So, n / (2 * 2 * …….. num_rows times) = 1
n = 2 ^ num_rows
num_rows = log2(n)
num_rows = O(log(n))
The merge algorithm compares the first element of both lists at each step, removes the smaller one from one of the lists, and appends it to the resulting list — after each step, the total size decreases by 1. Therefore:
No. of operations required to empty both lists = sum of sizes of both lists
An important point to note here — each element is present in each row exactly once. This implies that the sum of the size of all the lists in each row is exactly n.
Let’s say there are M lists in any arbitrary row, and the sizes of lists are s1, s2, .., sM.
Time required to merge consecutive pairs of the list in this row
= (s1 + s2) + (s3 + s4) + …… + (s(M-1) + sM)
= sum of the size of all the lists in the row = O(n)
The overall time complexity of merge sort = Time to merge all lists of a row * Number of rows
= sum of the size of all the lists in the row * num_rows
= O(n) * O(log(n))
= O(n log(n))
Let T(n) denote the time to sort a list of size n
T(n) = 2 * T(n / 2) + O(n)
The time required to sort a list of size n is twice the time needed to sort a list of half the size and then merge both the sorted lists in O(n) time.
Solving the above recurrence, we get T(n) = O(n log(n))
Merge sort always takes O(n log(n)) time to sort the list. Even if the list is already sorted, merge sort divides the list into n lists of size 1 and then merges them to get the sorted list of size n.
The space complexity of merge sort is O(n).
Space complexity only takes into account the auxiliary space we use to solve the problem. Space used to store the input information doesn’t matter here.
We used auxiliary space only for creating a temporary array to hold the result of merged lists. So, the space required is equal to the sum of the size of the lists being merged.
This, in the worst case, can be equal to n. Hence, the space complexity is O(n).
Question 1: Is merge sort an in-place sorting algorithm?
Answer: An in-place algorithm processes the input and produces the output in the same memory location that contains the input without using any auxiliary space. However, a small extra space for variables is allowed.
And so, merge sort is not an in-place sorting algorithm, because we use an auxiliary array to hold the merged list temporarily.
Question 2: Can we do something smarter and make the algorithm an in-place sort without making the time complexity worse than O(n log(n))?
Answer: No, we can’t. Here’s why — while merging, we need to read from and write to the same range of the array, and they will overwrite each other. So, we need an auxiliary array.
If we don’t care much about the time complexity, we can make the merge sort algorithm an in-place sort algorithm. The most efficient implementation of an in-place merge sort algorithm takes O(n * log(n)) to merge two lists and overall O(n * log(n) * log(n)) to sort the array.
Question 3: Is merge sort a stable sorting algorithm?
Answer: A sorting algorithm is said to be stable if the order of any two equal elements in the original list and the sorted list stays the same.
It depends on how we implement the algorithm. Most implementations of this algorithm produce a stable sort. While merging the left and the right list, if the first element of both lists are equal, select the element from the left list. This will produce a stable sort. Otherwise, the algorithm will not produce a stable sort.
If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
Article contributed by Taara Sinh Aatrey