Merge Sort
Merge sort is one of the most important sorting technique that works on Divide and Conquer algorithm, that means it works when we breaks down a problem into multiple subproblems recursively until they become simple to solve.
The Time Complexity of Merge sort is O(n*Log n).
Let’s learn this by implementing it.
Consider we have 2 sorted arrays as shown in the figure below.
Now, you must be thinking why are we taking two sorted arrays instead of just one unsorted array and just sort it out.
Hold on, we’ll get to that point as well.
For now, just consider we have two sorted arrays and we want to create one sorted array out of them.
How do we do that?
We will simply compare elements from each array and append the smallest one in the main array.
Starting from first element at index 0 we will compare
if 17<4 then append 4 (the smaller element ) in the merged array and increment the pointer to the next element as shown in the figure below.
We will keep on repeating this process until we get a nicely sorted array.
As you can see it is really simple to get a single sorted array out of two sorted arrays.
So, the purpose of taking two sorted arrays as an example was just to learn.
Now, here comes the original problem where we will consider an Unsorted array and sort it out using Merge sort.
Consider an unsorted array as shown in the figure below.
now we will understand how we can sort it using the concept we just learnt.
Step 1: Divide this array into 2 sub arrays.
Now, we have two arrays and we will try to merge them. But, we cannot do that until both the divided arrays are sorted. Therefore, we need to divide them further.
As you can see the sub array we got now are:
[21,38], [29,17],[4,25], [32,9]
Some of them are sorted whereas, some of them are not therefore, we need to divide them it further.
As you can see now we are left with sub arrays having single element in them. Can we merge them now? yes we can, by using the merging technique we learnt.
Consider all these single element arrays and compare and merge them as we did above.
As you can see we have sorted arrays and we can merge them now.
And finally, we’ve reached that point when we have two sorted arrays and we can easily merge them.
Now that we have understood the logic diagrammatically lets code all this step by step.
Step 1: Define a function that will merge two sorted arrays.
Step 2: Loop through elements of both arrays and append the smallest one in array and increment the pointer.
Lets run this and see what we got.
Although we got our merged sorted array but do you notice there’s something wrong here.
Yes ‘13’ is missing from the final array.
To fix this problem we need two more loops.
Voila! we got our merged sorted array.
Now, lets work with an un sorted array.
Define a function named mergeSort that will return a sorted array.
Step 1: Find the middle element:
By dividing the total length of array by 2 we can find the middle element.
Step 2: Divide array from middle element.
Step 3 : Name the divided arrays Left and Right.
Step 4: Sort and Merge them and return the final Sorted Array.
Although it works perfectly fine but it is not optimized in terms of space complexity.
Click here to get the optimized version of this code. Feel free to fork it and give it a star. 😄
PS: if you can optimize it further or want to add implementation of any other algorithm feel free to contribute to this repo.
Thankyou for reading if you have any queries comment below or reach out to me on LinkedIn. I’ll be happy to help.
