The question means to ask out of the comparision based sorting algos that we have , what is the lowest possible function corresponding to worst case scenario of number of comparisions..
So this is O(nlogn) as we have worst case for mergesort and heapsort = O(nlogn) which are comparision based algos.
We know that in merge() procedure of mergesort , we require comparision..And we know if we have no of elements in each of the 2 array as n/2 and hence the number of comparision in the worst case is given by = n/2 + n/2 = n
And in mergesort is called recursively 2 times on problem size of n/2..Hence the recurrence relation for no of comparision can be written as :
T(n) = 2 T(n/2) + O(n)
==> T(n) = O(nlogn)
Hence C) should be the correct answer..
