Assume that n is a power of two. Consider the following sorting algorithm:

SLOWSORT(A[1..n])

1: if n > 1 then

2: SLOWSORT(A[1 .. n 2 ])

3: SLOWSORT(A[ n 2 +1 .. n])

4: GATHER(A[1 .. n])

5: end if

GATHER(A[1 .. n])

1: if n = 2 then

2: if A[1]>A[2] then

3: swap A[1] A[2]

4: end if

5: else

6: for i 1 to n 4 do

7: swap A[i+ n 4 ] A[i+ n 2 ]

8: end for

9: GATHER(A[1 .. n 2 ])

10: GATHER(A[ n 2 +1 .. n])

11: GATHER(A[ n 4 +1 .. 3n 4 ])

12: end if

(a) Give an example proving that SLOWSORT would not correctly sort if we removed lines 6-8 in GATHER.

(b) Give an example proving that SLOWSORT would not correctly sort if we swapped lines 10 & 11 in GATHER.

(c) Prove by induction that SLOWSORT correctly sorts any input array (of size a power of two). (Hint: Formulate a claim for what GATHER is supposed to accomplish, and prove it.)

(d) Write a recurrence to count the number of comparisons made by GATHER on an array of size n. Write a recurrence to count the number of comparisons made by SLOWSORT on an array of size n. Solve these two recurrences to obtain an asymptotic expression for the number of comparisons done by GATHER and by SLOWSORT. No need to show your calculations