Merge Sort: Time and Space Complexity

Let’s analyze the time and space complexity of the bottom-up merge sort we just wrote. We will keep our assumption that $n$ is a power of $2$ .

Time Complexity

Recall from our analysis of the merge process that merging two adjacent sorted subarrays takes time linear in their combined length. Now look at a single pass of mergeSort for a given width. The merge calls in that pass do not overlap, and together they cover the whole array. So each element takes part in exactly one merge during the pass, and one pass costs $O (n)$ , no matter what the current width is.

Let’s count that for $n = 8$ :

When width = 1, we do four merges, each of combined length $2$ : $4 \times 2 = 8$ .
When width = 2, we do two merges, each of combined length $4$ : $2 \times 4 = 8$ .
When width = 4, we do one merge of combined length $8$ : $1 \times 8 = 8$ .

As width grows the merges get bigger, but there are fewer of them.

So how many passes are there? The width starts at $1$ and doubles every pass, giving $1, 2, 4, \dots$ , until it reaches $n$ . Doubling from $1$ to $n$ takes $lo g_{2} n$ steps, so there are $lo g_{2} n$ passes.

Putting the two together:

total time = (work per pass) \times (number of passes) = O (n) \cdot O (lo g n) = O (n lo g n)

This is a big improvement over the quadratic sorts from the last chapter. For an array of a million elements, $n^{2}$ is a trillion, and $n lo g n$ is around twenty million.

Space Complexity

Let’s split this into input space and auxiliary space, as usual.

The input space is $O (n)$ : the array we are sorting.

The auxiliary space comes from the merge method. The version we are using creates a temporary array to hold the merged result, then copies it back into the input array. The merge calls happen one after another, never at the same time, so only one temporary array exists at a time. The largest one comes from the final merge, which covers the whole array, so the temporary array has at most $n$ elements. The auxiliary space is therefore $O (n)$ .

That makes the total space $O (n)$ .