Source
Sorting algorithms are very important to know and implement. Today, I want to go over one of the most popular sorting algorithms called merge sort implemented in JavaScript.
What is Merge Sort?
Merge sort is one of the most popular sorting algorithms today and it uses the concept of divide and conquer to sort a list of elements. Meaning, it will divide the bigger problem into smaller problems and then solve each of the small problems in order to solve the bigger problem that we started out with.
Implementation
Planning
Now that we talked briefly about merge sort, let?s get right into the implementation of the merge sort.
(Note: I will be implementing the merge sort in JavaScript using recursion to sort an unsorted array in an ascending order.)
Before we get straight into writing code, let?s first identify the problem, plan, and come up with a solution. Let?s take an example array [10, -1, 2, 5, 0, 6, 4, -5]. This is obviously an unsorted array. That is exactly our problem and we must sort this array using merge sort. Merge sort requires dividing the problem into smaller problems. So let?s look at a diagram of how this will look like:
Notice that at each level we divide the array into two halves until we get bunch of single element arrays. This is the divide portion of the divide and conquer method. Then, we start merging and sorting the smaller arrays in a series of steps which is the conquer portion of divide and conquer.
Code
We now have identified the problem and have a plan on how we want to go about implementing the merge sort. So let?s code!
The code above will be our main function that will divide the given array into smaller arrays in every iteration of the recursive call. Don?t forget that recursion requires a base case in order to avoid infinite recursion. In our case, we have:
if (unsortedArray.length <= 1) { return unsortedArray; }
After we set up the base case, we can go ahead to identify the middle index and split the array into left and right just as we had in the diagram above. Then we need to merge the left side and the right side which we will implement now:
In the merge function above, we need to make sure we are sorting all the elements in the left and the right. The way we will do this is using a while loop. In addition, we will need to make sure we keep track of which element from each left and right we are comparing by using the variables leftIndex and rightIndex.
Within the while loop, we compare element in the left at leftIndex and element in the right at rightIndex. We can push the smaller of the two into our result array and move our cursor (leftIndex/rightIndex) to make sure we aren?t duplicating any comparisons.
Finally, we need to concatenate the result array with both left.slice(leftIndex) and right.slice(rightIndex). This is very important! If we don?t do this last step here, we will have an incomplete list of elements at the end because the while loop condition will fail once any one of the two cursors reach the end meaning the last element in either left or the right isn?t inserted into the result array.
That?s merge sort! It wasn?t that bad right?
If you would like to see the whole code, you can check it out here.
Thank you so much everyone for the read! You can also check my other JavaScript posts through my profile.
Basics of JavaScript:
Variable: https://medium.com/@timhancodes0281/basics-of-javascript-variable-3eb6f4f0af18
Data Types: https://medium.com/@timhancodes0281/basics-of-javascript-data-types-385bab24b51
JavaScript Fundamentals
Prototypal Inheritance: https://medium.com/javascript-in-plain-english/javascript-fundamental-prototypal-inheritance-9153ab434aae
ES6
Array Methods CheatSheet: https://medium.com/@timhancodes/javascript-array-methods-cheatsheet-633f761ac250
Rest & Spread Operators: https://medium.com/javascript-in-plain-english/rest-spread-operator-in-javascript-2da13aa942fb
Data Structure
What are Stack and Queue?: https://medium.com/@timhancodes/javascript-what-are-stack-and-queue-79df7af5a566
JavaScript Interview Topics
8 JavaScript Interview Topics: https://medium.com/@timhancodes/8-hot-javascript-interview-topics-4595458d22fc
Resources:
Github: https://github.com/yeb9925/sorting-algorithms
