My previous blog post was about an introductory sorting algorithm known as Bubble Sort. I wanted to dive into a more complicated sorting algorithm with a faster sorting speed. I decided to tackle merge sort. I couldn’t resist going back to a band I listened to in my youth called “The Promise Ring” because of their album “Very Emergency.” Clearly, the album title had something to do with that.
Merge Sort deals with a few different and important concepts that Bubble Sort doesn’t tackle.
Merge Sort has an average speed of O(n log n). What does this mean? Lets say you have 16 elements in an array. The computational time would be:
n = 16 multiplied by log base 2 of 16 which equals 4. In other words, 16 * 4 is 64 iterations.
Compare that to bubble sort with 0(n²) that would take longer with 16 * 16 being 256 iterations to get through the algorithm! As a general rule we like merge sort more for this reason.
A way to think about recursion is imagining a function or method calling itself inside of its own block of code. This will become more clear as we dive in so lets dig into merge sort:
1. The first step will be to take an array of elements and break the array into individual arrays that each have 1 element. For instance, if we have an array of [2,4,1,3] we want to have our first step of Merge Sort to break this array into 2 separate arrays being [2, 4] and [1, 3]. Then we would break each of these into individual arrays ,,,. Each of these individual arrays we can think of as sorted arrays that are sorted by the 1 element inside.
2. The next step will be to stitch back up the individual element arrays. The sorting happens when we start to stitch this back up.
We will do this recursively since we are performing the same operation over and over again breaking down and stitching up our initial array into pieces and then back into the sorted array.
Lets look at our code for Step 1:
What we’re doing here is breaking down the initial array into smaller pieces until we have their individual element arrays. We’ll step through this line by line below.
A) Lines 2–5: If the array length is less than 2 then we know the array is broken down to the individual element array so we can return it.
B) Lines 7–12: If the array is larger than 1 element item then we know we need to continue to break apart the array into smaller elements so we can get to our individual array element.
C) Line 7: Find the middle of the array so we can have a point to split the array into a left side and right side
D) Line 12: Call the merge function. However notice we’re calling mergeSort as arguments so we can continue to break down the array if it is not at it’s individual element yet.
E) I left in the console.log so when you try this at home you can follow and trace the path of how the recursion works. For me following the console.log helped me understand recursion and trace exactly the process happening is.
How do we merge these individual arrays back together? The key here is to compare the first element in each sorted array you’re stitching back up. Since the arrays will always be sorted, we know know comparing the array of index zero of each array will always allow us to know we are going in order.
A) Line 15: Our merge function takes two arguments, each a sorted array.
B) Line 16: This is where we will hold our array we are about to sort and stitch together.
C) Line 18–24: As long as each array has at least 1 element then we compare the first element of each array and add the smaller of the two to our new array.
D) Line 26–28 & Line 30–32: In step C above if one of our arrays is empty then that leaves us with 1 outstanding sorted array that we can now completely shovel into our new array.
One key takeaway that really helped me follow recursion was to start by messing around with using small arrays as input to fully trace through the recursion process. For instance if we have an array of [2,5,3] the process would be:
Since L is sorted we can move straight to R.
R[5,3] gets broken down to L, R.
We then merge these two which returns [3,5].
It’s now at this point we can merge(,[3,5]) and voila our output is [2,3,5].
Help me improve my code or teach me something! You can grab the repo below to mess around. I’ve also included a Ruby version as well in the repository.