Merge Sort: A Faster Sorting Algorithm

There are several well-known, fast sorting algorithms; merge sort, quick sort, and heap sort are the ones you are most likely to encounter in a future computer science course. Most of them involve techniques that we haven’t taught you yet, but merge sort can be written to be more accessible. Merge sort is built around the idea that taking two sorted lists and merging them is proportional to the number of items in both lists. The running time for merge sort is N log₂ N.

We’ll start with very small lists and keep merging them until we have a single sorted list.

Merging Two Sorted Lists

Given two sorted lists L1 and L2, we can produce a new sorted list by running along L1 and L2 and comparing pairs of elements. (We’ll see how to produce these two sorted lists in a bit.)

Here is the code for merge:

i1 and i2 are the indices into L1 and L2, respectively; in each iteration, we compare L1[i1] to L2[i2] and copy the smaller item to the resulting list. At the end of the loop, we have run out of items in one of the two lists, and the two extend calls will append the rest of the items to the result.

Merge Sort

Here is the header for mergesort:

Function mergesort uses merge to do the bulk of the work. Here is the algorithm, which creates and keeps track of a list of lists:

• Take list L and make a list of one-item lists from it.

• As long as there are two lists left to merge, merge them, and append the new list to the list of lists.

The first step is straightforward:

The second step is trickier. If we remove the two lists, then we’ll run into the same problem that we ran into in bin_sort: all the following lists will need to shift over, which takes time proportional to the number of lists.

Instead, we’ll keep track of the index of the next two lists to merge. Initially, they will be at indices 0 and 1, and then 2 and 3, and so on:

Here is our refined algorithm:

• Take list L and make a list of one-item lists from it.
• Start index i off at 0.
• As long as there are two lists (at indices i and i + 1), merge them, append the new list to the list of lists, and increment i by 2.

With that, we can go straight to code:

Notice that since we’re always making new lists, we need to copy the last of the merged lists back into the parameter L.

Merge Sort Analysis

Merge sort, it turns out, is N log₂ N, where N is the number of items in L. The following diagram shows the one-item lists getting merged into two-item lists, then four-item lists, and so on until there is one N-item list:

The first part of the function, creating the list of one-item lists, takes N iterations, one for each item.

The second loop, in which we continually merge lists, will take some care to analyze. We’ll start with the very last iteration, in which we are merging two lists with about N/2 items. As we’ve seen, function merge copies each element into its result exactly once, so with these two lists, this merge step takes roughly N steps.

On the previous iteration, there are four lists of size N/4 to merge into two lists of size N/2. Each of these two merges takes roughly N/2 steps, so the two merges together take roughly N steps total.

On the iteration before that, there are a total of eight lists of size N/8 to merge into the four lists of size N/4. Four merges of this size together also take roughly N steps.

We can subdivide a list with N items a total of log₂ N times using an analysis much like we used for binary search. Since at each “level” there are a total of N items to be merged, each of these log₂ N levels takes roughly N steps. Hence, merge sort takes time proportional to N log₂ N.

That’s an awful lot of code to sort a list! There are shorter and clearer versions—but again, they rely on techniques that we haven’t yet introduced.

Despite all the code and our somewhat messy approach (it creates a lot of sublists), merge sort turns out to be much faster than selection sort and insertion sort. More importantly, it grows at the same rate as the built-in sort: