Hi there,
In the previous last three sections we started having a look at Sorting Algorithms and this should be our 4th sorting Algorithm. Merge sort in the other is one the fastest out there much more faster than the already discussed Sorting Algorithms ie. bubble, selection & insertions Sort where we have to iterate through the given list before arranging either by swapping or replacing the current elements. in Merge sort we will do none of these and i must say out there it is considered one of the fastest yet complicated Sorting Algorithm but i bet to differ that once you get the only two concept involved in this search, in my opinion is the easiest i have come across so far. just note here that you will write a bit lengthy codes to achieve this but the process is just like playing a video game because at least in JavaScript it’s just repetitions of same process by changing the variables involved. Now what’s the trick ? as the name suggest just note you will merge at the end period. but before you do that it uses a divide and conquer strategy where you need to divide the given list into smaller parts, sort it before remerging the results, so in this algorithm you will need two solid methods one for merging a list and the order for recursively dividing the list before merging back. Enough of the imaginations let’s get down to it.
let’s look at a simple function that helps us to merge a two given list of array together. Note: We assume the arrays are already sorted in this case. after all they need to be sorted in any solution before being merge back.
// Merging two already sorted arrays
function merge(arr1, arr2) {
let results = [];
let i = 0;
let j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr2[j] > arr1[i]) {
results.push(arr1[i]);
i++;
} else {
results.push(arr2[j]);
j++;
}
}
while (i < arr1.length) {
results.push(arr1[i]);
i++;
}
while (j < arr2.length) {
results.push(arr2[j]);
j++;
}
return results;
}
merge([10,45, 62], [1, 2, 3, 5, 6]);
In our solution the function accepts two arrays that needs to be merged together to give a result we have declared altogether with the first element of the first array (arr1) i and the first element of the second array (arr2) j we use a while loop to make sure the index (i) never goes beyond the full length of it’s array and same applies to index j. we compare if the value of the current index (i) of the first array (arr1) id less than the second array (arr2) current value then keep the first array value into the results by pushing it to the next position else to same for the second array. because we will have a problem if one array appears to be longer than the other after using all elements of one list the other will still continue it’s job but against what ? remember we said they are already sorted ! so then they just have to be pushed directly to the rest of the results because there are nothing else to compare.
now that we have a way to merge let put this all together in our merge sort and create our recursive function with the divide and conquer approach to make sure we have the smallest breakdown possible to make it easy for our merge function to compare the two elements from different arrays.
// Merge function from earlier
function merge(arr1, arr2) {
let results = [];
let i = 0;
let j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr2[j] > arr1[i]) {
results.push(arr1[i]);
i++;
} else {
results.push(arr2[j]);
j++;
}
}
while (i < arr1.length) {
results.push(arr1[i]);
i++;
}
while (j < arr2.length) {
results.push(arr2[j]);
j++;
}
return results;
}
// Recrusive Merge Sort
function mergeSort(arr) {
if (arr.length <= 1) return arr;
let mid = Math.floor(arr.length / 2);
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
mergeSort([10, 58, 24, 76, 73]);
In a divide and conquer approach as one of the ways to solve Algorithms we are required to find a middle/median , left/low and right/high you remember Binary Search from the other sections ?
after finding those all we need here is to recursively keep repeating until we get a much more smaller lists to merge back to complete our solution. please do not forget that in a recursive function we always need our base case or the escape plan or else we go into a looping hell like spinning in a blackhole with a point of no return. What a nightmare ?
the reason why Merger Sort is supposed to be one of the fastest is because however we choose to execute it, it’s always on a worse case scenario of O(n*log n) log time on all standard which appears to be very good in the speed category. but a small trade off here on the space complexity of O(n) Linear because we needed to create more space to split the lists for our arrangement. if space wouldn’t be a problem then Merge sort should be the way to go or else the other earlier three do well in their Space complexities. Merge sort is the best suited to sorting a large amount of data even from an external source.
Okay Pal, Time up we need to say bye for now and don’t forget. read and solve more questions. Stay Safe 🙂