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.
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.
Read and analyse the example here before continuing in order to not get lost later on.
But the JS sort() method is MergeSort…
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 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)
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!
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!