previous | start | next

## 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:

previous | start | next