Algorithm Analysis/Merge Sort
Master Theorem Analysis
Merge sort has the recurrence relation:
due to the fact that each split operation splits the array of data into 2 parts of size .
The work done merging (the f(n) on the right) is linear, so .
Now we can apply the Master Theorem. The quantity c is:
If we examine the 3 cases, we can see that we fall into Case 2:
with k = 0. Then that implies:
Therefore, overall, merge sort is Theta(n log n):
AlgorithmsPart of Computer Science Notes
Series on Algorithms
Algorithm Practice and Writeups
Flags · Template:AlgorithmsFlag · e