Skip to main content
1 of 5
Charlie Parker
  • 3.1k
  • 21
  • 37

How many comparisons in the worst case, does it take to merge 3 lists of size n/3?

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.

Charlie Parker
  • 3.1k
  • 21
  • 37