Learn Merge Sort In 15 Minutes Or Less

For those of you who are just starting the process of learning computer science fundamentals, or just need a refresher for that upcoming interview, learning new algorithms can seem confusing or scary. In this article I want to demystify one of the most confusing algorithms for many computer science students, the merge sort, in 15 minutes or less. Let’s go!

Merge sort is a “divide-and-conquer” algorithm that divides its input into two halves, recursively calls itself on each of the two halves, and then merges the two sorted halves together. Say what?

Let’s begin by breaking down what “divide-and-conquer” actually means. A “divide-and-conquer” algorithm just simply refers to any algorithm that solves a problem using the following steps.

1. Divide the problem into a number of subproblems that are smaller instances of the original problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblem in a straightforward way.
3. Combine the solutions to the subproblems into the solution for the original problem.

Now that we have outlined the high-level steps of “divide-and-conquer” that we need to solve our problem we can now start to explain, in the case of merge sort, how we actually implement these steps in code. Starting from the top, we first need to explain the divide step. I already mentioned that merge sort “divides its input into two halves” to sort the input. In code that looks something like this.

Merge Sort Divide Step

Get the gist? The divide step was as simple as it sounded. We divided the input into two halves, leftHalf and rightHalf, and the function “recursively calls itself on each of the two halves”.

Now before I move on to the remaining steps we need to solve this problem, I want take a quick moment to explain what the idea behind why we divide the input into two halves in this way. The idea is simple. If I have two separate already-sorted lists of numbers, then it is very simple to combine, or merge, these two lists together into a single larger sorted-list that contains all of the numbers from the original two lists. In fact, as I am going to demonstrate, we can combine two already-sorted lists in linear time which in computer science is exceptionally fast. This idea is what drives the algorithm, and explains the reason we want to divide our single larger list into two halves.

Moving on to the “conquer” and “combine” steps of merge sort, we have already implemented the “conquer” step for trivial inputs. Who would have guessed?! Take a look at the if-statement on line 4 from the code sample mergeSortDivideExample.py above. If the list of numbers contains either zero or one number then the list is already sorted! In recursion, that is what we call our “base case” and is the mechanism that prevents the function from calling itself an infinite number of times and defines what is trivial. The question now is how do we “conquer” sub-problems of non-trivial sizes, such as for lists of two or more numbers. This is where we introduce our “combine” step. As I mentioned earlier, if we have two already-sorted list of numbers it is very simple to combine those two lists into a new sorted list that contains all of the numbers from the two original lists. Let’s take a look at how we can “combine” our sub-problems in code!

Merge Sort Combine And Conquer

And thats pretty much it! We have individually implemented the “divide”, “conquer”, and “combine” steps all that is left for us to do is put it all together.

Complete Merge Sort Code

And there you have it! The complete merge sort implementation you have all been waiting for. We just had to take the two code samples we already had, copy them into the same file, and make a single line addition to combine them together, which you can see on line 41. We have officially divided and conquered merge sort. Napoleon would be so proud.

One final note I want to make is on how efficient this algorithm is. To keep things simple, the runtime of this algorithm is O(n * log(n)) which makes this sorting algorithm one of the best generalized sorting algorithms available. If you want to learn more about runtime analysis, please let me know! I am interested in writing an introduction to runtime analysis in the future.

All in all, I really hope this helped you better understand this can-be confusing algorithm and if this article helped you in some way please share it with others.

Thank you for reading!

Did you enjoy this lesson? Give us a clap!

Want to know when I post more algorithm explanations? Follow my publication 15 Minute Algorithms!

Want to request an algorithm to be explained in 15 minutes or less? Message me on Medium Brandon Craig.