How many comparisons in the worst case, does it take to merge 3 lists of size n/3?
I was told it takes:
$$2(n-2) + 1 = 2n-3$$
However, I can't seem to figure out why.
The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?
Btw, I am not looking for an asymptotic answer.