Exercise 5.1. Consider the array S consisting of 8 elements in the following order: 8, 2, 6, 7, 5, 1, 4, 3. Find the total number of comparisons that each of the following algorithms takes on the below input:

a) Quicksort (Algorithm 15)

Algorithm 15 Algorithm QS(S). Input: A set S. Output: The set S in sorted order.

1: if |S| 6 1 then

2: return S

3: else

4: Let y be the first element in S.

5: Compare all elements of S to y.

Let

S1 = {x S {y} | x 6 y}

S2 = {x S {y} | x > y}.

(Elements in S1 and S2 are in the same order as in S.)

6: Return the list (in the following order): QS(S1), y, QS(S2)

b) MergeSort (Algorithm 12)

Algorithm 12 Algorithm Merge Sort(X, n)

1: MergeSort(X, 1, n)