Complexity of the Merge Process

Let’s analyze the time and space complexity of the merge process we just implemented. We will also discuss if there is a best vs worst case for this algorithm.

Time Complexity

Let $n$ and $m$ be the lengths of the two input arrays.

There is a single loop, and it runs once for each slot of merged. The merged array has $n + m$ slots, so the loop runs $n + m$ times.

The body of the loop is constant work. It checks at most three conditions, reads at most three elements, writes one element, and increments one index. None of that depends on the lengths of the arrays.

Constant work done $n + m$ times is $O (n + m)$ , so the merge runs in $O (n + m)$ time.

The cost of creating the auxiliary array

The step where we create the merged array, in Java, is also $O (n + m)$ because Java initializes the array with default values. In some other languages, this might be $O (1)$ if allocating the array does not initialize its elements. In Java, this initialization is just another constant factor on the $(n + m)$ cost, so it does not change the overall time complexity.

Space Complexity

The input space is $O (n + m)$ because we have to store the two input arrays. The auxiliary space is also $O (n + m)$ because we have to create a new array to hold the merged result. So the overall space complexity is $O (n + m)$ .

Best vs Worst Case

Is there a best vs worst case for merge? Let’s think through two scenarios.

The first one is when one of the arrays is empty. Say arr1 is empty. Then i >= arr1.length is true from the start, and every iteration runs merged[k] = arr2[j++]. So the merge is just a copy of arr2. That is one check per iteration instead of three, so it is cheaper, but the loop still runs once per element of arr2. The time is still $O (n + m)$ , with $n$ equal to zero here.

The second one is when every element of arr1 is smaller than every element of arr2. Then the merge copies all of arr1 first and all of arr2 after. We can detect this case up front with a single comparison. If arr1[arr1.length - 1] <= arr2[0], the largest element of arr1 is no larger than the smallest element of arr2, so all of arr1 comes first. Once we know that, we can copy the two arrays into merged without comparing anything, saving up to three condition checks per iteration. But we still have to copy every element, so the time is still $O (n + m)$ .

The loop runs $n + m$ times for every input. The input values decide which branch runs, and that changes the constant factor. They never change how many iterations there are. So the best case and the worst case of merge are the same, $O (n + m)$ .

In practice, special-casing these two scenarios is usually not worth the extra code. You would do it only if the arrays were large and you knew the special cases came up often.