Programming with JS: Merge Sort

Understanding data structures, algorithms and basic programming concepts is essential for one to become a better developer. Nowadays most of those problems are solved using modern tools and libraries, but having deeper knowledge in that area will definitely broaden your perspective of software development.

Personally, for me it was pretty hard to get a grasp on some of those concepts, because I was not using them in my day-to-day work. I’m writing this series to improve my own understandings on those topics and help other people like me.

What is Merge Sort?

Merge sort is one of the commonly used sorting algorithms in computer science. It is used by Firefox and Safari in their implementation of Array.prototype.sort() (remember how JavaScript behaves differently in different browsers?). It has good performance, it’s easy to implement and understand.

So how do you sort a list with merge sort, how does this algorithm work? It all revolves around the idea that it’s easier to sort two sorted arrays rather than one unsorted one. Once we have our two sorted arrays we start comparing their items one by one and adding the smaller item in our result list. Imagine that you’ve got two lists A and B. You compare A[0] to B[0]. Let’s say that A[0] is smaller — we add it to the result list and continue. Then we compare A[1] to B[0]. This time B[0] is the smaller one so we add it and continue comparing A[1] to B[1] and so on…

At the end of the sorting any left variables are concatenated at the end of our results list — since the A and B arrays are already sorted this will not cause reordering.

So how does it work?

The concept is fairly easy to understand but how do we reach a state in which we have two sorted arrays? Arrays of multiple items can’t be compared until they are sorted! We can achieve this by splitting the array into halves recursively until we reach a point in which we compare multiple pairs of single-item arrays.

[1, 5, 3, 9, 6, 4, 8]

[1, 5, 3, 9] | [6, 4, 8]

[1, 5] | [3, 9] [6] | [4, 8]

[1] | [5] [3] | [9] [4] | [8]

This is not the most comprehensive schema ever but you can see how the array is recursively split into smaller and smaller arrays until we reach the state in which we have only arrays containing a single item. At that point we start comparing them one by one and using the above mentioned concatenating method — sort our array.

[9, 3, 6, 4]

[9, 3] | [6, 4]

[9] | [3] [6] | [4]

[3, 9] | [4, 6]

[3, 4, 6, 9]

In other words, we split our array to it’s smallest pieces and then assemble them again but in the correct order. Here’s an implementation in JavaScript which utilizes the built-in slice function in order to get the parts of the array that we need.

Algorithms often don’t click on the first time you read about them. Spend some time on them — a day, two, a week or more until you properly understand them. Just reading through the code and copying it won’t help your thinking get better, so spend the extra time and wrap your mind around the concept.

Thank you for the read! You can check our my other JS articles in my profile or the more computer science-y topics here:

Programming with JS:

Recursion: https://hackernoon.com/programming-with-js-recursion-31371e2bf808Merge Sort: https://medium.com/@KondovAlexander/programming-with-js-merge-sort-deb677b777c0Binary Search: https://medium.com/@KondovAlexander/programming-with-js-binary-search-aaf86cef9cb3Insertion Sort: https://medium.com/@KondovAlexander/programming-with-js-insertion-sort-1316df8354f5