In my previous blog, I wrote how some simple sorting algorithms such as bubble sort, insertion sort, and selection sort work under the hood. In this blog, I will explain how to implement a higher-performance sorting algorithm merge sort.
The reason the merge sort algorithm is more performant than bubble sort or insertion sort is when we’re using these sorting algorithms we would always have to loop through the entire elements twice. So in the term of big O notation, it’s o of n square which is something we definitely want to avoid.
Using merge sort we’re dividing the elements into two parts and if the sub-array can still be divided then we go on. Until it’s one single element that we can’t do anything to it, we return it. Because of the dividing, our big O notation of merge sort is O(n*log N), which is a lot faster than basic sorting algorithms.
I mentioned before about dividing elements till we return one single element, what’s next? The following step is we join those single elements together, and while doing that, we compare them and place them in the right spot.
For now, we’ve had our structure of the merge sort function. We need one part to take charge of dividing and the other part to join them together and compare their value. Let’s dive into the second part first for it’s pretty easy to understand.
This function takes left and right arrays as its arguments because we’re joining them together. At end of this function, we will return the sorted array here so the first thing we do is to create a results array to store elements. While there are still elements in both arrays, we have some comparisons to do: if the first element in the left half is less than the first in the right half, we shift the element from left into the results array, else we shift the right one into the results array. Once one half doesn’t have an element we will exit the loop. However, there might still be one element in the other half so we have to take that into consideration. Because it’s greater than every element from before in the logic comparison so it must be the greatest. We just need to put it at last.
Now that we’ve finished the merge function, what’s the merge sort function like? Remember merge sort function’s job is to divide the original array into two half and over and over so here we will need recursion to the rescue.
This function takes an array as its argument and in the recursion, we need to define a basic case for it can be stopped at some stage. As we mentioned before the basic case is when there is nothing to be divided, thus the array’s length is one. The next step is to find the middle point of the array and slice it. I’m sure you have tons of ways to do that. The last step which is the essence of the whole algorithm is to return the merge function we just defined above and pass two merge sort function calls as left and right to it.
Boom! If you’re having second thoughts about this algorithm, I think a great way to think it through is to use a basic case like [4, 9, 0, 3] to test it and log it to see the value of variables. This is really fun! Thank you for reading!
