Q3 (4 points) This question tests your understanding of activation records as taught in class. (a) Assume that we want to apply Quicksort to sort the array A with 5 elements where the initial values of the array elements (from A[1] to A[5]) are A: 19 16 13 25 22 How many times do we push an activation record (for quicksort or partition) onto the runtime stack before the completion of the algorithm? Note that Quicksort(A, 1, 5) is the first activation record pushed onto the runtime stack. (b) Assume that we want to apply mergesort to sort the array A with 5 elements where the initial values of the array elements (from A[1] to A[5]) are A : 19 16 13 25 22 How many times do we push an activation record (for mergesort or merge) onto the runtime stack before the completion of the algorithm? Note that mergesort (A, 1, 5) is the first activation record pushed onto the runtime stack. Q4 (12 points) Assume that we use Quicksort (as in the textbook) to sort the array A with 5 ele ments where the initial values of the array elements (from A[1] to A[5]) are A : 19 16 13 25 22 . This question tests your understanding of the algorithm by following the element-wise com- parisons made in the execution of the algorithm. Here an element-wise comparison means the comparison of one element of the array with another element of the array or the key set in a particular step of the algorithm (Line 4 in Partition). Since the algorithm may move the elements of the array, you need to show the values of the elements being compared (rather than the form of A[i]). The first element-wise comparison is 19