What is the time complexity of MergeSort without its penultimate merge?
It will still take $O(n \log n)$.

There are four steps in mergesort.


Divide the list in half.
Mergesort the left half.
Mergesort the right half.
Merge the two together.


If I understand right, you're asking about removing the fourth step, in the final stage only (that is, not in any of the recursive calls).

In this case, you'll still have to do step 1 in $O(1)$, step 2 in $O(\frac{n}{2} \log \frac{n}{2})$, and step 3 in $O(\frac{n}{2} \log \frac{n}{2})$ (since steps 2 and 3 still call conventional mergesort, which is $O(n \log n)$).

So your total time complexity will be $O(1 + \frac{n}{2} \log \frac{n}{2} + \frac{n}{2} \log \frac{n}{2}) = O(n \log \frac{n}{2}) = O(n \log n)$.

The final merging only takes $O(n)$ time; it's the recursive part that's the real cost.