(a) Explain, and give pseudo-code for, the mergesort algorithm to sort an array A[ ] of integers into ascending order. Show the working of the algorithm on the array A = [ 4 8 9 2 1 736 ]. Give the tree representing the execution of the algorithm. State the worst case runtime of mergesort, of an array of n entries, in big-Oh notation, and give a justification of your answer. (9 marks) (b) Explain, and give pseudo-code for, the quicksort algorithm to sort an array A[ ] of integers into ascending order. Both mergesort and quicksort are in the divide-and-conquer class of algorithms, but differ in their approach to this. Briefly, describe how they take a different approach to the 'divide' and to the 'conquer' steps. (7 marks) (c) Suppose that the pivot is selected randomly from within the array. Briefly outline a proof that the resulting average case complexity is O(n log n) (4 marks)