previous | start | next

## Analyzing the Merge Sort Algorithm

- To understand why the merge sort algorithm is such a tremendous improvement, estimate the number of array element visits.
- First we consider the merge process. For a vector of n elements,
  - We must visit the first two elements of the halves and decide which is smaller (2 visits)
  - We must copy the smaller element to it's place in the sorted vector (1 visit)
  - We must copy the sort vector back into the original vector (2 visits)
- So the merge process takes 5n visits.

previous | start | next