Merge Sorting Algorithm
So you’re prepping for your next big coding interviews and you inevitably come across sorting algorithms. Unfortunately, not all sorting algorithms are made equal and some may be more complex then others. In this article, we will be taking apart a very particular sorting algorithm, the merge sort, and hopefully shed some light on it.
What is the Merge Sort?
Merge sorting is a divide and conquer algorithm that breaks down the problem into smaller more manageable ones. These smaller problems are solved and “merged” back together to solve the bigger problem. The merge sort algorithm does this by recursively dividing the array in half until each element is contained in its own array. The elements are then sorted and slowly merged back together in a sorted fashion. Take a look at the image below for a visual example of a merge sort.
Merge Sort Algorithm
Let’s start coding out the algorithm! First we are going to define a function called mergeSort that will be responsible for splitting our array in half recursively.
Next let us define the base case for our recursive mergeSort function. This will prevent the recursive function from continuing on forever and is essentially the ‘problem’ we know the answer to. We can now call mergeSort recursively on the left array and the right array and pass them in as arguments to a new function called merge .
This merge function will take two arrays as arguments and be responsible merging back the two arrays in sorted order.
Now with the merge function written, the final step is to realize we need to return the result of the merge function called in the original mergeSort function. This will yield our new sorted array. The final code looks something like this.
Final Thoughts
The time complexity of the merge sort algorithm is O(N log(N)) in average and worst case. The log(N) portion comes from splitting the arrays in half and the N from the comparisons done in merge .
The space complexity is O(N) due to the extra elements we are creating to merge and sort the arrays back together.
Merge sorting is definitely one of the faster sorting algorithms you could utilize with the O(N log(N)) runtime. Merge sorting is also a stable sorting algorithm meaning any unaffected elements in the output will in the same order as they were in the input. The benefits of stable sorting algorithms is that they are able to chain through multiple conditions.
Overall, the merge sort algorithm is very handy to have in your toolkit and can provide you with an efficient solution for a variety of sorting algorithm problems.
