There are 4 sorted list each of size 100, as n=400
List 1 = 100 records
List 2 = 100 records
List 3 = 100 records
List 4 = 100 records
Combining L1 and L2 needs 16 + 16 - 1 = 31 comparisons, in the worst case.
Combining L3 and L4 needs 16 + 16 - 1 = 31 comparisons, in worst case.
Now we have two sorted & merged files each of size 200, hence we need 32 + 32 -1 = comparison to merge these files into one file of size 64.
hence total comparisons are required : 2*31 + 63 = 125
Important point: In case of MERGE procedure, if there are two files, one with m records, and second with n records, then we need m+n-1 comparisons in the worst case.