a) Given the following list of numbers:

90 8 7 56 123 235 9 1 653 trace the execution for:

a.1) QuickSort (pivot = the first element).

a.2 MergeSort.

b) The processing time of an algorithm is described by the following recurrence equation (c is a positive constant):

T(n) = 3T(n/3) + 2cn; T(1) = 0

What is the running time complexity of this algorithm? Justify.

c) You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place. What is the worst-case complexity of your improved insertion sort if you take account of only the comparisons made by the binary search?

d) What is the running time complexity of the QuickSort when all elements of the array have the same value?