Consider the following variation on merge sort for the large values of 'n 'instead of recursing until 'n' is sufficiently small recur atmost a constant 'r' times and then use insertion sort to solve the 2r resulting sub problems.What is the running time of this variation
b)theta(n log n)
its given as theta (n2)
sorry I was wrong.
This may help you: http://gateoverflow.in/99455/sorting-algorithm
X->YZ , Y->XZ , ...