Analyzing the Merge Sort Algorithm
- To analyze the full algorithm, let T(n) denote the number of visits required to sort a range of n elements through the merge sort process.
- For each of calculation we will assume n = 2m.
- Because sorting each half will take
T(n/2) visits, we have:
- A similar analysis yields:
- Putting these two results together gives
us
- Repeating the process gives us:
