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