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