# Recursive algorithms and writing MergeSort in JavaScript

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.

# 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**.*

**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

**array next and we have an ordered array of length 2.**

*sorted*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

**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***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.

## A diagram to visualise the recursive order of MergeSort.

My implementation consists of two functions, a recursive`mergeSort`

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..

/*** mergeSort function takes unsorted array ***/// get array length // check array length is === 1, if is return array *vital* // split and copy array into two halves // recursively split the split arrays until array.length === 1/*** merge function takes two arrays and sorts and merges them ***/// The merge function declares a sorted array and two incremental counters. // Using while loops, if the increments are less than the length of their respective arrays check values and push in order into the ordered array. // keep in mind that one array may finish being sorted before the other so more code is required to sort the other array if this is the case. // // return the ordered array from the merge function.

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!