Merge Sort is a popular and efficient sorting algorithm that follows the divide and conquer approach, and this article provides an in-depth explanation of its implementation, analysis, and considerations.
Abstract
Merge Sort is a widely used sorting algorithm that divides the input array into two halves and recursively sorts them before merging them back together. This article covers the basics of Merge Sort, including its definition, the process of merging two sorted arrays, and how to implement it for both arrays and linked lists. The article also discusses the time and space complexity of Merge Sort, its advantages and disadvantages, and frequently asked questions. The implementation of Merge Sort is provided in both recursive (top-down) and iterative (bottom-up) approaches, with code examples and illustrations.
Bullet points
Merge Sort is a popular and efficient sorting algorithm that follows the divide and conquer approach.
The article covers the basics of Merge Sort, including its definition, the process of merging two sorted arrays, and how to implement it for both arrays and linked lists.
The article discusses the time and space complexity of Merge Sort, its advantages and disadvantages, and frequently asked questions.
The implementation of Merge Sort is provided in both recursive (top-down) and iterative (bottom-up) approaches, with code examples and illustrations.
The time complexity of Merge Sort is O(n log n) in all cases, while the space complexity is O(n) for the iterative approach and O(n log n) for the recursive approach.
Merge Sort is a stable and consistent sorting algorithm, but it is slower for smaller tasks and uses more memory space than other sorting algorithms.
Merge Sort is suitable for linked lists and can be implemented in a similar way to arrays.
The article includes code examples and illustrations to help readers understand the implementation of Merge Sort.
Merge Sort — Top Down and Bottom Up for Arrays and Linked Lists
Merge sort is one of the most efficient and popular sorting algorithms. It’s based on the divide and conquer approach, commonly used in computer science, practical, and easy to understand. We will go through the implementation details and the most important things to consider and remember while working with Merge Sort.
Merge Sort Intro
Content
What is the merge sort algorithm?
Merge two sorted arrays.
How does Merge Sort work?
Let’s write an algorithm and analyze it (top down & bottom up)
Let’s see how it works with linked lists, not just arrays
FAQ
Advantages
Disadvantages
What Is Merge Sort Algorithm?
Like Quicksort, Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, and this process of splitting the arrays continues till we have smaller arrays of one item, then the merge process starts by comparing the smaller split arrays and merging them together in sorting order, and by the end we will have a sorted array.
Merge Two Sorted Arrays
Before understanding how to sort arrays using merge sort, let’s understand the basic idea of how to Merge two arrays together?
Assume we have two sorted arrays arr1: [2,11,18,20,22] & arr2: [4,9,19,25], in order to merge them we will need one extra array to put the merge result in it.
The way we merge those two sorted arrays is very easy, just compare the two least elements and copy the smallest to the third array.
And to put this into steps:
Merge Two Sorted Arrays
Start with i index in the first array, j index in the second array and k index at the third.
Compare the value at i & j
Put the smallest value in k & move the smallest value index to the next.
Keep doing that till reaching the end of one of the arrays.
If there are remaining elements in one of the arrays just move them as it is to the third array.
Just to mention that the merge complexity here is O(n+m) where n is the length of the first array & m is the length of the second. We can say it’s nearly O(n).
Merge More than two sorted arrays can be done the same way, you can pick two arrays, merge them, and so on till reaching one sorted array.
What if those two arrays that we just merged were part of one array? How to sort them?
The procedure will be very similar to what we described above. Let’s take an example of the below array. Now we need to logically split it into two sorted arrays so we can merge them.
Apply the merge sorted array concept to one array
So to do that, we can define low (l), high (h) & mid (m) which we can use to define the boundaries of the first and second sub arrays.
Define the two sub-arrays boundaries
So to do the merge, we will need another array of the same size to add the merge results to it, then by the end, we can copy back the result from this auxiliary array to the original one.
Now and very similar to the first example of merging two sorted arrays, we will need to take i,j & k as shown below.
initializing the pointers
Then do exactly the same procedure as in the first example but instead of i,j,&k starting from 0, just make sure that i starting at l, j stats at m+1 & k starts at L as well.
And if we compared, the code of merging two sorted arrays, & the code of merge two sorted halves in one array, we will find it’s very similar as shown below:
compared, the code of merging two sorted arrays, & the code of merge two sorted halves in one array
This is the base of the merge sort. The merge sort is simply splitting an array to smaller halves till each array just have one item (which is sorted by nature), then start applying the merge to those sub arrays again till we reach one sorted array.
How Does It Work?
Merge sort is a recursive algorithm that works as per the below steps:
Split the input in half.
Sort each half by recursively using this same process.
Merge the sorted halves back together.
How splitting the array makes it sorted?
The array of just one element is sorted by design, so splitting the array to two halves till reaching the base case of just one item per array will make the array sorted.
Let’s write algorithm for merge sort
However merge sort is known to be recursive but we will go through how to write recursive & iterative version of it and what is the different between each.
In all cases, the merge part is the same & it’s exactly similar to merge one array with two sorted halves that we discussed above:
The merge part will be as described before:
The Recursive Approach (Top-down)
The code for the recursive approach is very easy, we just need to apply the three steps that we mentioned above and that should be it.
The split part is all logical in-pace, but to do the merge part you will need auxiliary array as we discussed earlier.
Time Complexity:
The time complexity of Merge Sort is O(n Log n) in all the 3 cases (worst, average and best) as the merge sort always divides the array into two halves and takes linear time to merge two halves.
n log (n) time complexity
Space Complexity:
When merging two sorted arrays into a single larger one, we need space to hold the merged result.
Since the arrays we’ll be combining have O(n) items, we’ll need O(n) space in total but because we are doing recursion calls so this extra array is goin to be copied log (n) times so the space complexity is O(n log n) here.
Notes about the space complexity:
If we look carefully, we see that we need less than O(n) space for some of the merges as when we’re merging two arrays with one element each, that requires O(1) space, but, by the time we get to the final merge, we’ll have two halves that each have n/2 items, so we’ll need O(n) space for the combined result.
If you look carefully, the current implementation uses more space than O(n) which is O(n log(n)) as for each recursive call, we’re passing in a copy of the input. And, since we might have O(log(n)) recursive calls before we hit the base case, that’s O(log(n)) copies of the input, but the space can be easily gets to reach O(n) with small changes.
The Iterative Approach (Bottom-Up)
The iterative part is based on the idea that a one item array is already sorted, so if we have a specific array we can treat each element in it as a sorted array, then apply the merge as usual.
Iterative Merge Sort
The Time complexity is O(n log n) as we do n merges for log n passes & the Space complexity is O(n) as we use auxiliary array in the merge routine. This version is better than the recursive one as we improved the space complexity.
Merge sort is preferred to sort linked lists not only arrays
Merge sort is recommended for sorting a linked list besides the insertion sort. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) impossible.
We will see how merge sort perform with O(nlogn) time complexity in linked list which is very similar to it’s performance while sorting arrays.
The idea of merge sort a linked list is the same of merge sort array & it can be done recursively or iteratively exactly the same way we did with the array.
Recursive Approach
Although merge sorting a linked list could be done using recursion or iteration, here we will go through the recursion approach only to simplify things & to not confuse people with many implementations.
In this approach, we will split the input linked list into two halves by making the next value of the middle node of the list equal to null, then we’ll call our recursive sort function on each half separately, at the end of each call we’ll merge the two sorted halves to get our linked list sorted.
It’s the exact similar approach to what we did with the arrays.
The Implementation
We will need to get the mid of the linked list then nullify it’s next so we have two halves, the left half and the right half, & once we break all the linked list to one item list, we will need to apply the merge routine. So there are 3 routines here:
Get the mid of the linked list.
Write the Merge method.
Apply the merge sort by splitting the linked list to halves then merge those halves to get a sorted linked list.
This is the single linked list node class:
publicclass SNode
{
publicint Val;
public SNode? Next;
public SNode(int val = 0, SNode? next = null)
{
this.Val = val;
this.Next = next;
}
}
And the merge sort for the linked list will be as shown below (I added some comments to describe more and clarify more points in the code itself but in general it’s straight forward and consists of three steps as I mentioned above)
Time Complexity
The time complexity is similar to what we discussed in the array merge sort. It’s O(n log n).
First, the GetMid(..) method has a complexity O(n) as we iterate over each node of the list at most once.
Second, the Merge method has a complexity O(n + m) as we iterate over the node of each list at most once.
Finally, the main MergeSort method has a complexity O(n log n) as in each call, we merge two lists with the complexity of O(n) and the depth of recursive tree will be log(n) because in each call we split our list into two halves.
Space Complexity
Space complexity is also very similar to the array approach, it’s O(n log n) as we create a new linked list each time we call the mergeSort, & because we call the merge sort log (n) times so the space complexity is O(n log n). The space complexity can be improved if we used iterative approach to be O(n) as there is no extra copy of the list will be needed during the merge.
FQA
What are the best sorting algorithms for linked lists?
Some times people prefer copying a linked list values to array then sorting it using something like quick sort and then move it back to a linked list as the array has much better cache performance than a linked list. If you’re going to sort a linked list so Merge Sort is good, also insertion sort is used for sorting linked lists but it comes with complexity of O(n²).
Is this Algorithm stable?
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other.
Is this Algorithm adaptable?
Simply we call algorithm adaptive if it takes advantage of the position of it’s elements to minimize the number of operations needed to perform the sort. Both top down and bottom up merge sorts are not adaptive as they always make O(n log n) operations. Even when an array is sorted, an array will be sub-divided, and the comparison will be made. There is a type of merge sort called natural merge sort which is adaptive by nature but it’s outside the scope of this topic.
Is this Algorithm in-place?
As you saw in the above illustration, merge sort is non to be not in-palace as in all cases we will need auxiliary array to perform the merge part. The space complexity sometimes reach to O(n log n) when we do it through the recursion as calling the extra array in the activation records will cause cause extra complexity for log n as we mentioned above and to improve that a bit we can use the bottom up technique to make sure the space complexity is O(n).
Is this Algorithm suitable for linked list?
This algorithm is suitable for linked list as it will give O(n log n) time complexity and can be done with the similar procedures as the array one.
When to use or not use it?
Don’t use it if the acquiring extra space is expensive, and use it if the stability of the sort is important.
Advantages
It is quicker for larger lists as it has time complexity of O (n log n)
It has a consistent running time, carries out different bits with similar times in a stage.
It’s stable algorithm.
Disadvantages
Slower comparative to the other sort algorithms for smaller tasks.
It’s not adaptive so it will go through the whole process even i he list is sorted
It uses more memory space to store the sub elements of the initial split list.
Finally
I hope you found this illustration useful. I tried to include as many clear examples and ideas as possible while keeping it simple and focusing on what’s important. Please feel free to leave your comments , suggestions, or any feedback you might have .