Order of Recursive MergeSort

Calculating the efficiency of MergeSort

Suppose that we have a list of 8 numbers. If we trace the migration of one value, it will be a member of the following sizes of lists: eight, four, two. The number of calls of mergeSort needed to sort one value into its final resting spot is log2N. If N = 8, then it will take three calls of the algorithm for one value to find its final resting spot.

We must apply log₂N steps to sort N elements in the list. The order of recursive Mergesort is O(N * log₂N) or O(N * log N).

What about the cost of merging the fragments of the list? The merge algorithm is a linear one, so when combined with the mergeSort routine, we have a O (N * log N) + O(N), which remains in the category of an O(N * log N) algorithm.