# 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 first merge for a list of 1024 things would be to merge 1024 single items into 512 lists of length two. Each merge would take ~2 units of work since there are two items in the new lists. 512 lists times 2 units of work = ~1024 units of work.

• The next level would be to merge those 512 lists of size 2 into 256 lists of size 4. Each merge in that level would take ~4 units of work. 256 lists times 4 units of work = 1024 units of work again.

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

Level Description Number of Lists Size of Each List Amount of Work
1 1024 lists of size 1
into 512 lists of size 2
512 2 512 · 2 = 1024
2 512 lists of size 2
into 256 lists of size 4
256 4 256 · 4 = 1024
3 256 lists of size 4
into 128 lists of size 8
128 8 128 · 8 = 1024
... ... ... ... ...
??? 2 lists of size 512
into 1 list of size 1024
1 1024 1 · 1024 = 1024

Note that 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:

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.

Like 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)$$. $$log_2(1024) = 10$$. 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) ≈ 16.61$$. (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:

$$\textrm{total work} = \textrm{work per level} · \textrm{number of levels}$$

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

$$\textrm{total work} = \textrm{n work} · log_2(n) \textrm{ levels}$$

Or:

$$\textrm{total work} = n·log_2(n)$$

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