Divide and Conquer Algorithms — Merge Sort

Often times in programming you‘ve got an array that is out of order, and values are just thrown in there because you know they’re important. Well, now I’d like to display those array values in a specific order. How might we do that?

Everyone who has ever shopped online has seen a list of products in front of them. Everyone has also seen that “Filter” button at the top of the screen as well! That filter button is a way to sort out the list of products you see in front of you, whether it be excluding certain categories of items or organizing the items with the least expensive items at the top (my personal favorite). This is why sorting algorithms are an important aspect of programming!

Now, you may be wondering, “Hey man, isn’t that what Array.prototype.sort() is for?”. Well silly human, just because an awesome language like JavaScript has this figured out for us already, that doesn’t mean we shouldn’t understand what is going on behind the scenes there! Algorithms are important to know, and relying on built in functions does not give you an in-depth understanding of programming, this is why we’re going to be covering the Divide and Conquer programming paradigm!

Divide and Conquer

Divide and Conquer is a programming paradigm that Merge Sort and Quicksort algorithms use. It is an algorithm based on recursion, and it is broken down into 3 main steps:

1. Divide the problem into subproblems that are simply smaller instances of the original problem.
2. Conquer the subproblems by solving them recursively. If the problem is small enough, then that is the base problem.
3. Combine the solutions to the subproblems to the solution for the original problem

Here’s what it looks like:

Let’s take a look at a sorting problem, and solve it using the Merge Sort algorithm.

Problem

Our problem is that we have an array of numbers that is out of order. Our job is to put these numbers in order from least to greatest. Here is the array:

[4, 8, 7, 2, 11, 1, 3]

Here’s how were going to do this:

1. Split the given list of numbers into two halves (roughly equal halves)
2. Continue dividing the subarrays in the same manner until you are left with only single element arrays
3. Starting with the single element arrays, merge the subarrays so that each merged subarray is sorted
4. Repeat step 3 until we end up with a single sorted array

We are first going to write our merge() function that takes two sorted subarrays and transforms them into one sorted array. Remember, both subarrays are already sorted, we are not just merging them together.

merge()

In the function above, we take two sorted subarrays (left, right) and merge them to get a single sorted array. First, we create an empty array (arr). We then pick the smaller of the smallest unpicked element in the left and right subarrays and push them into the empty array. We need to only check the first elements in left and right subarrays since they are both sorted.

While doing this, we delete the picked element from the subarray (using shift()). We continue until one of the subarrays becomes empty. After that, we push the leftover elements of the non-empty subarray into the main array.

As we now have the conquer aspect of our divide and conquer paradigm, the only part left to do is to keep splitting our arrays until we end up with arrays that only contain one element.

mergeSort()

Here, we identify the midpoint and split the array into two subarrays using splice(). If there is an odd number of elements, the left one gets a smaller number of elements. We divide until we are left with single element arrays (array.length < 2). After that, we start combining the subarrays using our merge() that has already been defined.

Now that we’ve got our Merge Sort functions written out, lets see them solve our problem!

input

output

That’s awesome! We’ve sorted our array from least to greatest using our Merge Sort algorithm!

The beauty of this algorithm is not seen when testing it on a small array such as the example we used above. This algorithm really shines when using it on large arrays, cutting the time it takes for the function to run by a large amount.

I hope you now understand the importance of Merge Sort, as well as the Divide and Conquer paradigm. I hope to see you again in the future for more algorithm learning and practice. Happy coding!

Resources

Divide and conquer algorithms (article) | Khan Academy

Merge Sort in JavaScript