Making Sense of Merge Sort [Part 1]
Tags: computerscience, beginners, sortingalgorithms, algorithms
Published: 2017-09-23 22:01:39

---
title: "Making Sense of Merge Sort [Part 1]"
published: true
tags: computer-science,beginners,sorting-algorithms,algorithms
canonical_url: https://medium.com/basecs/making-sense-of-merge-sort-part-1-49649a143478
cover_image: https://thepracticaldev.s3.amazonaws.com/i/hupa0lhio7hbx2pib9ow.png
description: Divide and conquer algorithms!
---

If you’ve been reading this series sequentially, then there’s a good chance that over the course of the past few weeks, you’ve thought more about sorting things than you’ve ever thought about before! At least, that has certainly been the case for me. I haven’t started dreaming about sorting algorithms just yet, but I’m expecting that it might happen soon.

Well, guess what? We’re not quite halfway through this series yetâ€Š–â€Šand we’re not quite halfway through sorting algorithms yet, either! However, we _are_ at a turning point our algorithm adventure. So far, we’ve talked about some of the most commonâ€Š–â€Šand sometimes thought of as the more “simple”â€Š–â€Šsorting algorithms. We’ve covered [selection sort](httpshttps://dev.to/vaidehijoshi/exponentially-easy-selection-sort), [bubble sort](https://dev.to/vaidehijoshi/bubbling-up-with-bubble-sorts), and [insertion sort](https://dev.to/vaidehijoshi/inching-towards-insertion-sort). If you take a closer look at these algorithms, you might notice a pattern: they’re all pretty slow. In fact, all of the sorting algorithms that we’ve explored thus far have had one thing in common: they’re all pretty inefficient! Each of them, despite their little quirks and differences, have a _quadratic_ running time; in other words, using Big O notation, we could say that their running time is _O(nÂ²)_.

This commonality was completely intentional–surprise! The order in which we’re learning these topics is actually pretty important: we’re covering sorting algorithms based on their _time complexity_. So far, we’ve covered algorithms with a quadratic runtime complexity, but from this point forwards, we’ll be looking at algorithms that are significantly faster and more efficient. And we’ll start off with one of the most fun (albeit a little more complex) sorting algorithms there is!

Don’t worry, we’re going to break it down, step by step. I suppose that step one is telling you what this algorithm is called! It’s time for you to meet my new friend: merge sort.

### Divide and conquer algorithms

You might have heard merge sort discussed or referenced in the context of a technical interview, or a computer science textbook. Most CS courses spend a decent amount of time covering this topic, and for some reason or another, this particular algorithm seems to pop up quite a lot.

Interestingly, however, merge sort was only invented (discovered?) in 1945, by a mathematician named [John von Neuman](http://history-computer.com/ModernComputer/thinkers/Neumann.html). In the grand scheme of things, merge sort is still a fairly new algorithmic approach to sorting. But hang on a secondâ€Š–â€Šwe still don’t know what it is yet!

Alright, time for a definition. The **_merge sort algorithm_** is a sorting algorithm that sorts a collection by breaking it into half. It then sorts those two halves, and then merges them together, in order to form one, completely sorted collection.

![](https://cdn-images-1.medium.com/max/1024/1*T4lE_CveG7rAkEziwKtpAw.jpeg)<figcaption>Merge sort: a definition</figcaption>

And, in most implementations of merge sort, it does all of this using _recursion_. But hold that thought for nowâ€Š–â€Šwe’ll come back to recursion in just a moment.

> The basic idea behind merge sort is this: it tends to be a lot easier to sort two smaller, sorted lists rather than sorting a single large, unsorted one.

We’ve already seen how sorting through one large, unsorted list can end up being slow. If we think back to [selection sort](https://dev.to/vaidehijoshi/exponentially-easy-selection-sort), we ran into the issue of having to iterate through the list multiple times, selecting the smallest element and marking it as “sorted”. With [bubble sort](https://dev.to/vaidehijoshi/bubbling-up-with-bubble-sorts), we again had to pass through the list many, many times; each time, we compared just two elements at a time, and then swapped them. Bubble sort was more obviously slow since we had to make so many swaps! And then there was [insertion sort](https://dev.to/vaidehijoshi/inching-towards-insertion-sort), which was kind of acceptable if our list was already mostly sorted. But if it wasn’t, then we basically were forced to iterate through a list and, one item at a time, slowly pull out the smallest element and insert it into its correct spot in a sorted array.

This is where merge sort fundamentally differs from all of these other sorting algorithms. Let’s take a look at an example to help illustrate this.

![](https://cdn-images-1.medium.com/max/1024/1*ZFpPwH6_ssRu5p8tM9T-vQ.jpeg)<figcaption>Merge sort theory: how does itÂ even?</figcaption>

In the image here, we have a single, unsorted list. Conceptually, merge sort asserts that instead of a one unsorted list, it’s a lot easier to sort and join together two _sorted_ lists. The idea is that if we could somehow magically end up with two sorted halves, then we could very easily merge those two sorted sublists together. Ultimately, if we did our merging in a smart, efficient way, we could end up with one sorted list at the end of it all.

Hopefully, at this point, you’re wondering how on earth merge sort can just “magically” split and sort two halves of our list.

> Hang on for a secondâ€Š–â€Šwe’re programmers! Intrinsically we know that, at the end of the day, there really is no magic at play here. There’s something else going on under the hood, and it’s probably an abstraction of something else.

In the case of merge sort, that abstraction is something called **_divide and conquer_** (sometimes referred to as **_d&c_** ). The divide and conquer technique is actually an _algorithm design paradigm_, which is really just a fancy way of saying that it’s a design pattern that lots of algorithms use! In fact, we’ve already seen this exactly paradigm before, way back when we were first learning about the [binary search algorithm](https://dev.to/vaidehijoshi/leaf-it-up-to-binary-trees).

So what does the divide and conquer paradigm entail, exactly? Well, for starters, an algorithm that uses the divide and conquer strategy is one that divides the problem into smaller subproblems. In other words, _it breaks down the problem into simpler versions of itself_.

The basic steps of a d&c algorithm can be boiled down to these three steps:

1. **Divide** and break up the problem into the smallest possible “subproblem”, of the exact same type.
2. **Conquer** and tackle the smallest subproblems first. Once you’ve figured out a solution that works, use that exact same technique to solve the larger subproblemsâ€Š–â€Šin other words, solve the subproblems recursively.
3. **Combine** the answers and build up the smaller subproblems until you finally end up applying the same solution to the larger, more complicated problem that you started off with!

![](https://cdn-images-1.medium.com/max/1024/1*34hoECtIduXaHJOM3I7Z_Q.jpeg)<figcaption>The rules of divide and conquer algorithms</figcaption>

The crux of divide and conquer algorithms stems from the fact that it’s a lot easier to solve a complicated problem if you can figure out how to split it up into smaller pieces. By breaking down a problem into its individual parts, the problem becomes a whole lot easier to solve. And usually, once you figure out how to solve a “subproblem”, then you can apply that _exact_ solution to the larger problem. This methodology is exactly what makes recursion the tool of choice for d&c algorithms, and it’s the very reason that merge sort is a great example of recursive solutions.

### Spotting recursion in the (algorithm) wild

Understanding divide and conquer in theory is one thing, but its usefulness tends to be far more obvious if we can see it in action. Let’s take a look at how we can use recursion to divide and conquer the illusive merge sort algorithm!

![](https://cdn-images-1.medium.com/max/1024/1*1IIg51aqZDJE2gwnfvJ1pQ.jpeg)<figcaption>Merge sort: inÂ practice</figcaption>

In theory, we understand that merge sort splits up an unsorted list, sorts the two halves, and merges them together.

But how does this algorithm really work in practice?

Well, now that we know what exactly that “magic” is that goes on behind the scenesâ€Š–â€Šthat is to say, the abstraction that’s responsible for sorting the two sublist halves–we can finally try and understand how it works. It’s time for us to apply the divide and conquer paradigm to merge sort and figure out what’s actually going on inside this algorithm!

We’ll start with a simple example, and we won’t actually worry about sorting any values just yet. For now, let’s try to understand how the divide and conquer methodology comes into play. We know that first need to divide and break up the problem into the smallest possible “subproblem”, of the exact same type. The smallest possible “subproblem” in our situation is our base caseâ€Š–â€Šthe point at which we’ve basically solved our problem. In terms of sorting items, the base case is a sorted list. So, we can divide our large problem (and our unsorted list) into it’s smallest possible pieces.

![](https://cdn-images-1.medium.com/max/1024/1*Gu7ROST8xBe8mpvwVd0nUg.jpeg)<figcaption>Step 1:Â Dividing</figcaption>

In the example above, we just continue to divide our problem into smaller subproblems. We start off with one, unsorted list. Then we break that up into two, unsorted lists. We can divide that even further, into four lists. And then we can break that down again, into eight lists. At this point, we’ve got eight lists, and each list has only _one_ item in it.

We can’t divide these any further, can we? So, we’ve arrived at our smallest possible subproblem, and our base case: a sorted list, with one single item in it. You might remember from previous sorting algorithms that a list with only one item in it is, by definition, considered sorted. This is because there’s literally nothing elseâ€Š–â€Šno other itemâ€Š–â€Što compare it to!

Okay, now we have eight _sorted_ lists, and each one has only one item in it.

According to divide and conquer, we know that the next step is to tackle our smallest subproblems first. Once we can determine a solution that works, we’ll apply that same solution to solve the larger subproblemsâ€Š–â€Šin other words, we’ll use recursion.

So, let’s start by combining (merging) two items together at a time. Since we have eight sorted lists, let’s combine each list with its neighbor. When we do this, we’ll put the items in the correct, sorted order.

![](https://cdn-images-1.medium.com/max/1024/1*weVLB4M6m9J7wiPZXDasrg.jpeg)<figcaption>Step 2: Conquering!</figcaption>

Nice! That was pretty cool. We took our eight, sorted lists, and merged them together to create four sorted lists. Then we took _those_ four lists, and merged them together to form two sorted lists.

Oh, waitâ€Š–â€Štwo sorted lists? Hang on…that sounds familiar. I think we just figured out the “magic” behind merge sort! How rad is that?!

Now, since we have two sorted lists, we can finish up our merge sort by _merging_ them together.

![](https://cdn-images-1.medium.com/max/1024/1*sqF24VkW6zydJ0yNnieq7w.jpeg)<figcaption>How does merge sort work with recursion?</figcaption>

There are a few reasons that divide and conquer actually works so well in implementing merge sort. For starters, the fact that a list with a single item is, by definition, a “sorted” list is what makes it easy for us to know when we’ve hit our smallest possible “subproblem”. When this algorithm is implemented in code, this ends up being the base case for determining when the recursion should end. We’ve talked about recursion before in the context of [binary trees](https://dev.to/vaidehijoshi/leaf-it-up-to-binary-trees); in that situation, the base case is a single leaf nodeâ€Š–â€Šin other words, when you can’t break down a subtree into any smaller possible parts. The same idea applies here: when we can’t break down our list into any smaller possible parts, and when we only have one item that is sorted, we’ve hit our recursive base case.

Another reason that divide and conquer works here is once we know how to merge two items together and have figured out the logic behind that, we basically can just keep reusing that same logic and continue applying it to every built-up sublist that we merge together.

> This is exactly what makes recursion so powerful: once we’ve figured out how to solve the problem of merging two lists together, it doesn’t matter if the list has one element, or a hundredâ€Š–â€Šwe can reuse the same logic in both scenarios.

Let’s take a look at one more exampleâ€Š–â€Šthis time, we’ll use actual numbers that we’re trying to sort. In the drawing below, we have an unsorted list with eight numbers. We can start by dividing the unsorted collection into two sublists. We’ll just continuing dividing until we hit our base case.

![](https://cdn-images-1.medium.com/max/1024/1*p6pvuQ0mKCYkx3ZXv6ufgw.jpeg)<figcaption>Merge sort in action: step 1â€Š–â€Šdividing</figcaption>

Okay, now we’re down to the smallest possible subproblem: eight lists, and each has one, sorted item within it. Now, we just need to merge two lists together. We’ll merge each sorted list together with its neighbor. When we merge them, we’ll check the first item in each list, and combine the two lists together so that every element is in the correct, sorted order.

Easy-peasy! We got this.

![](https://cdn-images-1.medium.com/max/1024/1*V1QaE66T3SgIIO-jv0-fHw.jpeg)<figcaption>Merge sort in action: step 2â€Š–â€Šmerging</figcaption>

Great! Once we started merging two lists together, we didn’t have to think too much more when it came to merging those two sorted sublists, did we? We used the same technique to merge lists with four items as we did when we merged lists with only one item.

Okay, illustrations are greatâ€Š–â€Šbut what would this look like in code? How would we even be able to spot the recursive part of a merge sort algorithm if we saw one in the wild?

### Recursion at work

We already know that a recursive algorithm is one that conceptually uses _the same solution_ to solve a problem. When it comes to code, this can effectively be translated to a function that _calls itself._

In the code belowâ€Š–â€Šwhich is adapted from Rosetta Code’s JavaScript [implementation](https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#JavaScript) of merge sortâ€Š–â€Šwe can see that the mergeSort function actually _calls itself._

```javascript
function mergeSort(array) {
  // Determine the size of the input array.
  var arraySize = array.length;
 
  // If the array being passed in has only one element
  // within it, it is considered to be a sorted array.
  if (arraySize === 1) { 
    return; 
  }
 
  // If array contains more than one element,
  // split it into two parts (left and right arrays).
  var midpoint = Math.floor(arraySize / 2);
  var leftArray = array.slice(0, midpoint);
  var rightArray = array.slice(midpoint);
 
  // Recursively call mergeSort() on 
  // leftArray and rightArray sublists.
  mergeSort(leftArray);
  mergeSort(rightArray);
  
  // After the mergeSort functions above finish executing,
  // merge the sorted leftArray and rightArray together.
  merge(leftArray, rightArray, array);
  
  // Return the fully sorted array.
  return array;
}

function merge(leftArray, rightArray, array) {
  var index = 0;
 
  while (leftArray.length && rightArray.length) {    
    if (rightArray[0] < leftArray[0]) {
      array[index++] = rightArray.shift();
    } else {
      array[index++] = leftArray.shift();
    }
  }
  
  while (leftArray.length) {
    array[index++] = leftArray.shift();
  }
  
  while (rightArray.length) {
    array[index++] = rightArray.shift();
  }
}
```

There are a few things going on here, and we won’t dive into all of them today (don’t worry, we’ll come back to it next week!). For now, let’s just look at what makes this algorithm recursive in nature. We can see that we’re taking in an input array, and splitting it as close as we can to the centerâ€Š–â€Šin this case, we call it midpoint.

Then, we take those two halves (leftArray and rightArray), and we actually pass those in as the new input arrays to the _internal_ calls to mergeSort. Guess what? This is recursion in action!

We can think of it recursion kind of like [Russian babushka dollsâ€Š](https://www.google.com/search?q=babushka+dolls&source=lnms&tbm=isch&sa=X&ved=0ahUKEwiNwtCnhafUAhXIKWMKHYpvC8EQ_AUICygC&biw=1280&bih=634#imgrc=pv0kNXKNcXWAMM:)–â€Šor like boxes with smaller boxes within them.

![](https://cdn-images-1.medium.com/max/1024/1*z5MT4e1sp1Lx3VBCrAgAWA.jpeg)<figcaption>How recursion works inside of an implementation of a mergeSort function</figcaption>

A mergeSort function ultimately has two functions inside of it:

1. a merge function, which actually combines two lists together and sorts them in the correct order
2. and a mergeSort function, which will continue to split the input array again and again, recursively, and will also call merge again and again, recursively.

Indeed, it is _because_ merge sort is implemented recursively that makes it faster than the other algorithms we’ve looked at thus far.

![](https://cdn-images-1.medium.com/max/1024/1*oXvb3coX1acjONgeJqbJkQ.jpeg)<figcaption>Recursive vs iterative solutions</figcaption>

But why is this? And just how _much_ faster is merge sort, exactly? Well, you’ll get the answer to both of those questions next week! In part 2 of this series, we’ll look at the runtime complexity of merge sort, how this recursion actually makes it more efficient, and how merge sort stacks up against other algorithms. Until thenâ€Š–â€Šhappy merging!

### Resources

Merge sort comes up quite a lot in computer science curriculums, technical interviews, and even in textbooks. There’s a wide array of resources for this particular algorithm simply because it’s one of the more tricky sorting algorithms to understand. If some of this still doesn’t make sense to youâ€Š–â€Šor if you’d like to see more examplesâ€Š–â€Štry taking a look at these different resources below.

1. [Binary Search & Merge Sort](https://www.andrew.cmu.edu/course/15-110-m12/applications/ln/Unit05PtBPtC.pdf), Department of Computer Science, Carnegie Mellon University
2. [Mergesort](http://www.mcs.anl.gov/~itf/dbpp/text/node127.html), Ian Foster
3. [Merge Sort](https://www.youtube.com/watch?v=sWtYJv_YXbo), Harvard CS50
4. [Merge sort algorithm](https://www.youtube.com/watch?v=TzeBrDU-JaY), mycodeschool
5. [External Sorting](http://www.geeksforgeeks.org/external-sorting/), GeeksForGeeks

* * *


_This post was originally published on [medium.com](https://medium.com/basecs/making-sense-of-merge-sort-part-1-49649a143478)_