Sorting and Searching

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.