Merge Sort: Best and Worst Case

Recall how we got the $O(n\log n)$ running time for merge sort. It is the product of two things: the number of passes, and the work per pass. So let’s ask whether the input order can change either one.

Does the input order change the number of passes?

No. The number of passes depends only on width, which starts at $1$ and doubles until it reaches $n$. That gives ${\log }_{2}n$ passes no matter what the values in the array are.

Does the input order change the work per pass?

No again. Within a pass, the work is done by the merge calls, and we showed that the loop in merge runs the same number of times on every input. The values only decide which of the two subarrays the next element comes from. So each pass is $O(n)$ regardless of the input.

Since neither the number of passes nor the work per pass depends on the input, the running time is $O(n\log n)$ on every input.

That is very different from insertion sort, for example, and it has an advantage and a disadvantage.

• The advantage is that merge sort is predictable. No input makes it take quadratic time.
• The disadvantage is that merge sort cannot take advantage of an input that is already sorted or nearly sorted. Insertion sort finishes a sorted array in $O(n)$. Merge sort does its full $O(n\log n)$ of work regardless.

Could we give merge sort a better best case?

We could, if we were willing to add a check. Recall from our analysis of the in-place merge that when the last element of the left half is already less than or equal to the first element of the right half, the two halves are in order and there is nothing to merge. If we skipped a merge in that situation, an already-sorted array would skip every merge and finish in $O(n)$.

The textbook version of merge sort does not do this, and we will leave it that way. The code stays simpler.