Section 8.17 Merge Sort Efficiency

So how efficient is Merge Sort? Well, for starters, remember that merging n items takes \(O(n)\) work. In other words, merging 5 items takes ~5 units of work, merging 20 items, takes ~20 units of work, etc… Now let’s do a rough analysis of how long it takes to do a merge sort on a list of length 1024.

All the hard work takes place as we merge the lists back together:

The table below shows this and the pattern for the rest of the level:

Note that at each level the work is ~1024 units of time - exactly the number of items in the full list. Thus we can say each level takes \(O(n)\) work.

The only other thing we need to figure out is “How many levels are required?” The table above skips a few steps in the middle. We could go back and add them in - starting with 1024 items the levels would look like this:

1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

That is 10 levels of merging to group 1024 single items into one list of 1024.

You can use Wolfram Alpha website to calculate log base 2 by typing something like “log2(1024)”. Try it below:

As we saw with binary search, that progression - dividing by 2 repeatedly until we reach 1 - can also be determined by the mathematical function \(log_2(n)\text{.}\) \(log_2(1024) = 10\text{.}\) Using that, we could calculate the number of levels of merges required to do a Merge Sort on a list of 100,000 items: \(log_2(100,000) \times 16.61\text{.}\) (Since we can’t do 16.61 merges levels, we would call that 17.)

The formula also allows us to write a general formula for the overall work required for a Merge Sort. Starting with:

We know that sorting n items will require \(log_2(n)\) levels and each level will take n work:

Or:

Merge Sort requires \(O(n \cdot log_2(n))\) work to sort a list of size n.