Question

Determine the number of comparisons (as a function of n and m) that are performed in merging two ordered files a and b of sizes n and m, respectively, by the merge method, on each of the following sets of ordered files:

{eq}a. m=n and a[n/2] < b[1] < b[m] < a[(n/2)+1] \

b. m=1 and b[1] < a[1] \

c. m=1 and a[n] < b[1]

{/eq}

{eq}displaystyle a[i]

{/eq}