JavaScript: Understanding Merge Sort and its Implementation.
In this article, we will learn to implement Merge Sort in JavaScript.
If you are reading this article then probably there are good chances that you are preparing for a Job Interview, so we will focusing more on the implementation part of Merge Sort rather than its depth study.
Yaa Ya, we all know that the Merge sort is based on the beautiful concept of computer science Divide & Conquer concept. Let’s try to understand how?
Think what would be easier for you to sort an array of 200 elements of an array of 500 or an array of 250 elements or an array of 125 elements ……… till we get the array of 2 elements
I believe your answer would be an array of 2 elements, if not try to imagine if the array contains lakhs of enteries.
That's was the “Divide” part of Divide & Conquer. We divide the array into smaller arrays and try to sort them first.
Now imagine you have 2 arrays that are already sorted will it be not easy to combine them in such a way that the resultant array is sorted and was the “Conquer” part.
The merge sort algorithm is a sorting algorithm that sorts a collection by breaking it into half. It then sorts those two halves, and then merges them together, in order to form one, completely sorted collection.
Implementation Time:
Part 1: Divide part
function mergeSort(arr){
if(arr.length==1) return arr; //base condition
let middle = Math.floor(arr.length/2)
let leftArray = mergeSort(arr.slice(0,middle))
let rightArray = mergeSort(arr.slice(middle,arr.length))
return mergeArray(leftArray,rightArray)
}We will break the array into 2 parts from the middle and assume that pass left array to the same function with an assumption that it will return the sorted left array, and the same goes for the right part. Now we have arrays that are sorted we need to merge them in such a way that the resultant array is sorted let assume there is some magical function “mergeArray” which will do our task.
Let’s do some calculation suppose you have 128 elements in the array, how many times “mergeSort” function would have been called we will study this is analysis at the last.
Part 2: Conquer part
function mergeArray(a,b){
let c =[]
while(a.length && b.length){
c.push(a[0]>b[0]?b.shift(1):a.shift(1))
}
c = [...c,...a,...b]
return c
}This part is pretty simple, we take a temporary array c and compare the 0th index of both the arrays, whichever value is smaller we remove that element from the array and push that value in the c and keep on doing this till any of the 2 arrays is not empty. Now we need to push all the remaining elements of the second array which is not empty into c.
Once the new array is filled up with all the elements it's time to return this array.
Wrap Up
array = [132,413,5135,13531,1]
console.log(mergeSort(array)) // [1, 132, 413, 5135, 13531]Ta da 🎊🎊🎊🎊, that all was the implementation of Merge Sort.
Analysis: For 128 elements the first division would be of 2 arrays of 64 elements then each array would be divided into 2 arrays of 32 elements and soo on, If you observe the process properly it would be a tree structure and there would be a total log2(N) divisions for each level there will be mergeArray would be called for N times, the total complexity of the algorithm comes to be Nlog2(N)
