Suppose that the program of Fig. 7.2 uses a partition function that always picks a[m] as the separator v. Also, when the array a[m],... ,a[n] is reordered, assume that the order is preserved as much...

Suppose that the program of Fig. 7.2 uses a partition function that always picks a[m] as the separator v. Also, when the array a[m],... ,a[n] is reordered, assume that the order is preserved as much as possible. That is, first come all the elements less than v, in their original order, then all elements equal to v, and finally all elements greater than v, in their original order.


a) Draw the activation tree when the numbers 9,8,7,6,5,4,3,2, 1 are sorted.


b) What is the largest number of activation records that ever appear together on the stack?

Fig. 7.2