When Mergsort merges two sorted lists of
sizes m and n into a sorted list of
size m+n, it requires how many comparisons?
m+n-1m+nmnn+1O(\log m + \log n)O(\log m + \log n + 1)Mergeing compares two records, and selects the smaller.
Each record gets selected once, and each selection requires a comparison.
Except, the last record does not need a comparison to be selected because there is no longer anything to compare it to.