Question: Suppose the version of the divide-and-conquer two-dimensional closest-pair algorithm in which, instead of presorting input set P, we simply sort each of the two sets Pl and Pr in nondecreasing order of their y coordinates on each recursive call.
Assuming that sorting is done by mergesort, set up a recurrence relation for the running time in the worst case and solve it for n = 2^k.
I am not sure how to solve the question. Can anyone help me?