Recall that merging two sorted lists of size n requires at least n-1 comparisons in the worst case. Why is this the case?

Consider the decision tree model for comparison-based algorithms. What is the minimum height of a decision tree that can merge two sorted lists of size n?

Prove that any comparison-based algorithm for merging two sorted lists of size n must make at least 2n-1 comparisons in the worst case by analyzing the decision tree's number of leaves and the information-theoretic lower bound.