8.16. 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 lets 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:

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.

Th 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.