Photo by Lance Grandahl on Unsplash

Searching and Sorting Algorithms in Javascript — Part 5 (Merge Sort).

Merge sort is one of the more “Complex” sorting algorithms. As far as algorithms go, most times, the efficiency of the algorithm is inversely proportional to the ease of implementation of the algorithm. What I mean by that is that, the more efficient the algorithm gets, the harder it’s implementation (or at least, the concept) gets.

So, how does Merge sort work?

The main Idea behind this algorithm is that, an array of exactly 1 element is already sorted. So, given an array of multiple elements, we start to split the array into half until we get to arrays of 1 element each, then we start to merge each array into one another. I know that sounds like rubbish but, Let me show you what I mean (Carefully take a look at the following pictorial representation. I’ll explain what it is below the image).

Pictorial representation of the array splitting process

We started with an array of 8 elements and we started halving until we arrived at arrays of single elements. Note that at each halving stage, there’s always a right and a left, we then proceed to separately half the left and right until we arrive at the last stage.

Next, we start joining our single arrays except that, while joining, we make sure we sort the items in that array. Below is a pictorial representation of the process:

Pictorial representation of the array merging process

During this merging process, the following occurs:

1. We take two arrays (which are each sorted) and we try to merge them together
2. The final array produced at any stage has it’s elements sorted

If none of the above process is clear to you, I totally understand. It can be overwhelming at first, it was overwhelming for me at first as well but, I’ll encourage you to checkout the demonstration of this algorithm by watching this quick youtube video - https://www.youtube.com/watch?v=4VqmGXwpLqc. When you’ve finally digested how it works, come back and see how to write it in code.

At this point, I want to believe the algorithm is a bit clearer (if you took the time to checkout the referenced Youtube video referenced above). If not, just continue and read till the end.

How does the above pictorial representation work in code (you might ask)?

Well, we have 2 components in our code:

1. A merge function: This is basically the function that will serve the purpose of merging 2 already SORTED arrays
2. A merge sort function that does the whole actual merging for us.

The merge sort function itself is a recursive function as you’ll see in the code below.

Implementation of the merge function that merges 2 sorted arrays

Please, make sure you understand how both function works. Just know that the aim of the first function is to merge 2 already SORTED arrays into a larger SORTED array.

The aim of the second function however (the mergeSort function) is to:

1. Split the array until we get only single element arrays
2. Merge them till get our final sorted array.

Wheew!!! That was quite a lot to take in. You might be dying to ask, why do we have to learn such a complicated algorithm since you already know selection, bubble and insertion sort?

Well, I’m happy to tell you that the merge sort algorithm scale well for very large arrays. If you compare it to bubble sort, it’s about 20x faster than bubble sort (😱). It has a time complexity of O(N log N) compared to O(n²) for bubble sort.

Well, that’s it guys… If you don’t understand yet, try to read again and watch the video recommended in this post.
See you on the next one !!!