Mergesort: Like You're 5

Merge sort is based around the principle that merging two sorted sets into a single sorted set is easy. If we take two sorted sets, S1 and S2 such that:

S1 = [1, 3, 4] and S2 = [2, 5]

And we want to merge them into a new set, S3, which is also sorted, here's how we do it the mergesort-way. First, start with the two original sets, S1 and S2, and have S3 be empty.

S1 = [1, 3, 4] and S2 = [2, 5] and S3 = []

What we want to do is add the elements to S3 in order so that once the merge is complete the sorting is already finished. So the first step is to add the smallest element to S3. Since the sets S1 and S2 are already sorted, the smallest elements of each are their first elements. All we need to do to find the smallest element is look at the first element of each and take whichever is smaller. So we look at:

      v                  v
S1 = [1, 3, 4] and S2 = [2, 5]

and notice that 1 is smaller than 2, so we can be certain that 1 is the smallest element of either of the sets. So we can take that out of S1 and add it as the first element of S3. After that we just repeat the process and compare the first elements again.

      v               v
S1 = [3, 4] and S2 = [2, 5] and S3 = [1]

In this case 2 is less than three, so we append it to S3 and repeat.

      v               v
S1 = [3, 4] and S2 = [5] and S3 = [1, 2]

Three is less than 5, so the next step looks like:

      v            v
S1 = [4] and S2 = [5] and S3 = [1, 2, 3]

4 is less than 5, so we append it to S3, leaving S1 empty.

S1 = [] and S2 = [5] and S3 = [1, 2, 3, 4]

Now that S1 is empty, we can just append the entire contents for S2 on to the end of S3, since they're already in order, and we end up with S3 as the complete, sorted merge of S1 and S2

S1 = [] and S2 = [] and S3 = [1, 2, 3, 4, 5]

Of course this whole time you've been wondering, how does this apply to sorting in general? We don't normally get the luxury of starting with two sorted lists so this whole thing is stupid and you're stupid for writing it. Well, although I'm going to have to disagree about the me being stupid part, I see where you're coming from. The way it works, just like with quicksort, is that it has to be applied recursively. Here is a trivial example, let's use merge sort to sort this small set:

S1 = [4, 1, 3, 2]

You should notice two differences between this and the starting conditions of the other example: It's one list instead of two, and it's not sorted. The first difference is easy to fix, let's just split it in half down the middle.

S1 = [4, 1] and S2 = [3, 2]

There's one problem solved, now let's work on the other. Neither S1 nor S2 is sorted, so we'll have to sort them. The way we do that is, of course, with mergesort! Let's start with S1.

S1 = [4, 1]

Once again we've got one unsorted set, and once again, we begin by splitting it in half.

S1 = [4] and S2 = [1]

Now the sets only contain one element each, which makes them sorted by definition! Just like in quicksort, the base case of mergesort is that a set containing 1 or 0 elements is automatically sorted. Now we just need to merge them like we did before, comparing the first element of each set and adding the smaller one to the result. I won't bore you with the step by step of the merge process since we already went over it in depth, but just trust me when I say that the result will look like this

S1 = [] and S2 = [] and S3 = [1, 4]

Just to clarify, I've left the empty sets S1 and S2 in just to illustrate that we got to this result the same wasy as before; by taking elements one at a time out of S1 and S2 until they were both empty. Now we've got one of our subsets sorted and we can bring it back a level to get here:

S1 = [1, 4] and S2 = [3, 2]

Now we just need to do mergesort on S2 and we'll be able to merge them together. Once again we split S2 into two sets:

S1 = [3] and S2 = [2]

Do the merge process on them again:

S1 = [] and S2 = [] and S3 = [2, 3]

Take this result back a level:

S1 = [1, 4] and S2 = [2, 3]

Now just merge this whole thing:

S1 = [] and S2 = [] and S3 = [1, 2, 3, 4]

And we're done!