15.4 Mergesort

In our last example, we'll analyze merge sort, another cool sorting algorithm.

First, let's remind ourselves of selection sort, which we will initially use as a building block for merge sort.

Selection sort works off two basic steps:

  • Find the smallest item among the unsorted items, move it to the front, and ‘fix’ it in place.

  • Sort the remaining unsorted/unfixed items using selection sort.

Let's introduce one other idea here: arbitrary units of time. While the exact time something will take will depend on the machine, on the particular operations, etc., we can get a general sense of time through our arbitrary units (AU).

Hold onto this thought for later analysis.

Now that we have selection sort, let's talk about merging.

Say we have two sorted arrays that we want to combine into a single big sorted array. We could append one to the other, and then re-sort it, but that doesn't make use of the fact that each individual array is already sorted. How can we use this to our advantage?

It turns out, we can merge them more quickly using the sorted property. The smallest element must be at the start of one of the two lists. So let's compare those, and put the smallest element at the start of our new list.

Now, the next smallest element has to be at the new start of one of the two lists. We can continue comparing the first two elements and moving the smallest into place until one list is empty, then copy the rest of the other list over into the end of the new list.

To see an animation of this idea, go here.

Selection sort is slow, and merging is fast. How do we combine these to make sorting faster?

Having two sorted arrays is a good step, but we need to put them together. Luckily, we have merge. Merge, being of linear runtime, only takes ~64 AU. So in total, splitting it in half, sorting, then merging, only takes 512 + 512 + 64 = 1088 AU. Faster than selection sorting the whole array. But how much faster?

Exercise: Show why the time is ~640AU by calculating the time to sort each sub-list and then merge them into one array.

What if we halved it again? And again? And again?

Eventually we'll reach lists of size 1. At that point, we don't even have to use selection sort, because a list with one element is already sorted.

This is the essence of merge sort:

  • If the list is size 1, return. Otherwise:

  • Mergesort the left half

  • Mergesort the right half

  • Merge the results

So what's the running time of merge sort?

  • To get the top layer: merge ~64 elements = 64 AU

  • Second layer: merge ~32 elements, twice = 64 AU

  • Third layer: ~16*4 = 64 AU

  • ...

  • The top level takes ~N AU.

  • Next level takes ~N/2 + ~N/2 = ~N.

  • One more level down: ~N/4 + ~N/4 + ~N/4 + ~N/4 = ~N.

Last updated