Welcome to CS

Section8.17Merge 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 Merge 1024 lists of size 1
into 512 lists of size 2
512 2 512 × 2 = 1024
2 Merge 512 lists of size 2
into 256 lists of size 4
256 4 256 × 4 = 1024
3 Merge 256 lists of size 4
into 128 lists of size 8
128 8 128 × 8 = 1024
??? Merge 2 lists of size 512
into 1 lists of size 11024
1 1024 1 × 1024 = 1024
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
1
http://www.wolframalpha.com/
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:
\begin{gather*} \textrm{total work} = \textrm{work per level} \times \textrm{number of levels} \end{gather*}
We know that sorting n items will require $$log_2(n)$$ levels and each level will take n work:
\begin{gather*} \textrm{total work} = \textrm{n work} \times log_2(n) \textrm{ levels} \end{gather*}
Or:
\begin{gather*} \textrm{total work} = n \cdot log_2(n) \end{gather*}
Merge Sort requires $$O(n \cdot log_2(n))$$ work to sort a list of size n.