Hint: Mergesort

Question: Consider the algorithm we outlined in class for merging two lists. In the worst case, how many element comparisons will this algorithm take to merge an array with n elements and an array of m elements? The answer should be exact; do not use big-O or Theta notation to approximate.

Hint: After each comparison, the algorithm places one element into the resulting array.

Answer.


Hint: Mergesort / Arrays algorithms / Review questions / 15-211 A, B