Let us consider both Merge Sort and Insertion Sort in which we want to sort an input array of n integers in ascending order. What will be the worst case asymptotic upper bound on the running time if (i) the input is already sorted in ascending order (ii) the input is already sorted in descending order (iii) the input contains n copies of the same number State and justify your answer for each scenario and algorithm