Let us consider n=2k
let at level i , L1 and L2 is merged,
An item in L1 is compared maximum times when all the items in L2 is less than item in L1.
Say at leaf level k (level at smallest subproblem having one element in each list), an item is compared only once when merging.
at level k-1 an item is compared twice when merging.
say at level i , it is compared n/2i times
at level 2 it is compare n/2 times and after merging we get the sorted array of our problem
total comparison of an item = n/2+ n/(22)+. . . . + .n/(2k) where n/(2k) =1
= n*(1-1/(2k))
= n - n/(2k)
= n-1
Answer is c) n-1.
Correct me if I am Wrong