Recursive algorithms and writing MergeSort in JavaScript

John Diprose
Feb 24 · 5 min read

An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

This article is for intermediate developers who want to broaden their horizon in Computer Science and understand the concept of recursion providing ideas into techniques developed by programmers and mathmaticians that came before us. Learning recursion is not only enjoyable but will help you with potential white board coding sessions during job interviews.

If you do not have a thorough understanding of many vital programming concepts — variables, function calls, scope, and of course loops, I would recommend getting hold of these skills first.

Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945, it is still used today because of its efficiency and general purpose.

As a JavaScript developer, you will find yourself regularly writing and using algorithms from a simple for loop iterating a DOM classlist, to using the sort() method to organise some data for an application or site. This article is written primarily for intermediate JS developers who would like to gain better insight into core CS concepts or develop their knowledge on them further.

Recursion.

Recursive — relating to or involving the repeated application of a rule, definition, or procedure to successive results.

Recursion in programming is a technique to repeatedly apply an action to a data set, so It’s a function that repeatedly calls itself with updated properties until a condition is met, returning from the function with the required result.

Example.

Read and analyse the example here before continuing in order to not get lost later on.

This is an explication to demonstrate recursion. Iin reality you do not want to use recursion for this application rather using split() or a for loop. It should demonstrate the principles quite clearly.

But the JS sort() method is MergeSort…

Depending on the implementation used by the JavaScript engine, the Array.sort() method will likely use MergeSort. By all means use Array.sort() in production and don’t feel that using a custom implementation is going to speed things up, this is simply for fun, learning, and self development. So that in check, let’s get started.

MergeSort explained.

Fundamentally MergeSort works by splitting an array in half and those halves in half until each array has only one element within it.

Once you have a load of arrays with one element in each, you can start the sort and merge process.

Comparing each element’s value, length, size etc we can determine which element is the first (or lowest value) then push it into a new array named sorted.

MergeSort visualised — https://www.mcs.anl.gov/~itf/dbpp/text/node127.html

For an example, imagine an array with two values [7,1];

After just the first iteration (which will be the only split in this case), we have our two arrays with one element in each, we compare the values in each array and push the lowest value into the sorted array we can knowingly push the other value into the sorted array next and we have an ordered array of length 2.

In our recursive function we will have two tracking or incrementing values starting at 0 that signal where in each array the value is we are currently comparing. If value 0 in array 0 is smaller than value 0 in array 1, we push value 0 into the sorted array and increment value 0 by one, making the same comparison again. This is where while loops come in particularly handy as we can perform a loop without knowing the quantity of iterations needed to perform. (As one array may empty before another)

While loops

When I was new and nieve to programming, I didn’t properly appreciate the benefit of while loops, opting instead for a for loop with `break` or `continue` statements. The benefits really stood out when writing my own algorithms and doing algorithm challenges.

For more information, visit: While & for loop differences in detail.

Write your own MergeSort!

With the information I’ve shared above, I now recommend you try to write your own mergesort implementation in JavaScript. I will leave you will a list of comments from my MergeSort implementation to guide you, please feel free to attempt different techniques within the division and sorting functions though keep in mind the general process will be very similar.

Following the numbered steps, you can see that one side of the inputted array is split completely into one element arrays first, then merged into a two element array. The process continues on the opposite side of the initial array until we end up with a two element sorted array there too. Finally, these two sorted arrays are sorted again and merged into the output array. By doubling the amount of array elements from 4 to 8, we would have four recursive instances of the function splitting the array. I think knowing the route your recursive function is running is valuable in writing more complicated recursive functions. Also it’s fun to visualise these things and understand them properly.

My implementation consists of two functions, a recursivemergeSort function that divides the inputted array and a merge function that sorts the elements. The return value from the mergeSort function can be saved to a new variable and accessed as a sorted version of the inputted array.

While i’m not going to share my sourcecode with you at the end of this article as you should challenge yourself to write your own. If you are stuck, I can share my implementation with you in the comments.

So without further ado, here are some instructional steps to guide you..

For more information on writing your own algorithm implementations I find GeeksForGeeks to be a great resource — https://www.geeksforgeeks.org/fundamentals-of-algorithms/

Thanks for reading and I hope this may have helped you in some way!

15