I had a hankering to learn a new frontend framework so I decided to build something - a sorting visualizer. While I'm far from finished, I wanted to share some fun things that I've come across so far relative to the algorithms.
I have two previous blogs that also deal with this material. One of them focuses on the fundamentals of bubble sort and the other discusses how I managed to visualize bubble sort as it is sorting.
This whole idea of creating a web app that visualizes a sorting algorithm has taught me many things, but specifically two: how to tackle problems in a new framework and how these algorithms actually function.
Merge Sort was certainly the most difficult of the sorting algorithms to visualize for me. Rather than utilizing async/await keywords to manipulate the timing of the call stack, I ended up recording some data after each operation in the algorithm and then iterating over the recorded data to visualize what had just happened. Sounds strange, but trust me it's pretty cool!
However, before I dive into that awesomeness I want to go over a basic example of merge sort to share my interpretation of this algorithm.
Let's kick it off by assuming we are given an unsorted array of integers and we are asked to sort them with merge sort.
The basic premise behind merge sort is that it will repeatedly (AKA recursively) split the given data in half until it consists of arrays of length 1. Why is that? Because an array of length 1 is in fact a sorted array. Then merge sort will begin to merge these arrays back together until it has one array of sorted values.
Let's walk through this process step by step with an actual array of unsorted integers to see this beauty in action. Here is our array:
[ 4, 5, 2, 7, 8, 6, 3, 9 ]
Now let's split it in half.
[ 4, 5, 2, 7 ] [ 8, 6, 3, 9 ]
Then we'll split each of those arrays in half.
[ 4, 5 ] [ 2, 7 ] [ 8, 6 ] [ 3, 9 ]
Finally, we'll split these arrays in half.
[ 4 ] [ 5 ] [ 2 ] [ 7 ] [ 8 ] [ 6 ] [ 3 ] [ 9 ]
As you can see all our array has been split into sub arrays so many times that we now have 8 arrays of length 1. Like we had clarified before, an array of length 1 is a sorted array, so now let's start merging them back together.
From here we will iterate over two arrays and compare the first indexes and return a new array with the two values in their sorted order. Starting with the first two arrays and compare their indexes. Since 4 is less than 5 it will go first and we'll merge the two arrays into one:
[ 4, 5 ] [ 2 ] [ 7 ] [ 8 ] [ 6 ] [ 3 ] [ 9 ]
Continuing, we'll do the same with 2 and 7:
[ 4, 5 ] [ 2, 7 ] [ 8 ] [ 6 ] [ 3 ] [ 9 ]
Notice the next two arrays contain the values 8 and 6. Since 6 is less than 8 we'll merge them together putting 6 before 8:
[ 4, 5 ] [ 2, 7 ] [ 6, 8 ] [ 3 ] [ 9 ]
And finally we'll compare the arrays containing the values 3 and 9 and merge them together:
[ 4, 5 ] [ 2, 7 ] [ 6, 8 ] [ 3, 9 ]
So far so good, nothing to outlandish going on here. In fact we're already on our way home! We'll simply repeat this compare and merge process all of the way back up.
If we compare the first two indexes of the first two arrays we'll see that 2 is less than 4 so it will go first. Then we'll compare 4 and 7: 4 is less than 7 so it will be next. We'll then compare 5 and 7 and put 5 next, then 7.
[ 2, 4, 5, 7 ] [ 6, 8 ] [ 3, 9 ]
Repeating this process with the next two arrays we see that 3 is less than 6, 6 is less than 9, 8 is also less than 9 so our merged array would look like this:
[ 2, 4, 5, 7 ] [ 3, 6, 8, 9 ]
Last step, again repeat the process we already have set up: iterate over each array, comparing the first values and merged them in a sorted order and we'll have our merged sorted array!
[ 2, 3, 4, 5, 6, 7, 8, 9 ]
It is certainly a divide and conquer approach. With the recursive nature you can also see a tree like structure appear from the recursive dividing and merging. Before we wrap up let's go over the time and space complexity involved here.
As far as time complexity, we start by splitting the array into a smaller arrays until we reach arrays of length 1 for each value. For starters we have an O(N) amount of operations. Then we eventually combine each of these arrays back together, iterating over each value to merged them into our sorted array which is also O(N) operations. So now we are at O(2N) which simplifies back to O(N). Finally, considering the fact that we cut the array in half and recursively repeat this algorithm on each half until we have length 1 we actually compute this O(N) amount of operations log(N) times resulting in an O(N log(N)) time complexity.
The space complexity can vary depending on how you implement the algorithm, but for this example of recursively calling merge sort and creating new sub-arrays we can see that we will divide and merge each value which gives us a space complexity of O(N). And we will repeat these steps on each recursive call (sub-array) which will come out to roughly O(log(N)). Combining these two considerations together we'll end up with a space complexity also of O(N log(N)).
Merge sort is super interesting and there are a few ways to implement it. Obviously, there will be several recursive calls going to separate and then merge all of these arrays in a tree like fashion which we can dive into next when I go over how to visualize this killer algorithm. I hope this has been helpful and has demystified the inner workings of this great sorting algorithm!
Top comments (0)