Summary

This context provides an explanation and implementation of the merge sort algorithm in JavaScript.

Abstract

The context discusses the merge sort algorithm, a popular sorting algorithm that uses the concept of divide and conquer to sort a list of elements. The author explains how merge sort works, breaking down a larger problem into smaller ones and solving each of them to arrive at the solution for the original problem. The context then proceeds to implement the merge sort algorithm in JavaScript using recursion. The implementation involves dividing the given array into smaller arrays in every iteration of the recursive call and merging them back together in a sorted order. The author provides code snippets and explanations for each step of the implementation process.

Bullet points

Merge sort is a popular sorting algorithm that uses the divide and conquer method.
The algorithm works by dividing the problem into smaller problems, solving each of them, and then merging the results to arrive at the solution for the original problem.
The context provides an implementation of the merge sort algorithm in JavaScript using recursion.
The implementation involves dividing the given array into smaller arrays in every iteration of the recursive call and merging them back together in a sorted order.
The author provides code snippets and explanations for each step of the implementation process.
The context includes a link to the full code implementation on GitHub.

Merge Sort Algorithm in JavaScript

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://readmedium.com/basics-of-javascript-variable-3eb6f4f0af18

Data Types: https://readmedium.com/basics-of-javascript-data-types-385bab24b51

JavaScript Fundamentals

Prototypal Inheritance: https://readmedium.com/javascript-fundamental-prototypal-inheritance-9153ab434aae

ES6

Array Methods CheatSheet: https://readmedium.com/javascript-array-methods-cheatsheet-633f761ac250

Rest & Spread Operators: https://readmedium.com/rest-spread-operator-in-javascript-2da13aa942fb

Data Structure

What are Stack and Queue?: https://readmedium.com/javascript-what-are-stack-and-queue-79df7af5a566

JavaScript Interview Topics

8 JavaScript Interview Topics: https://readmedium.com/8-hot-javascript-interview-topics-4595458d22fc

Resources:

Github: https://github.com/yeb9925/sorting-algorithms