1.)

Prove that the following recursive algorithm actually sorts its input.

3PASS-SORT ( A[0],...,A[n-1] ):

if n=2 and A[0] > A[1] swap A[0] with A[1]

else (n>2)

m = ceiling(2n/3)

3PASS-SORT( A[0],...,A[m-1] )

3PASS-SORT( A[n-m],...,A[n-1] )

3PASS-SORT( A[0],...,A[m-1] )

 

b) Suppose we replaced ceiling by floor. Is your correctness proof for a) still valid?

If it is, explain, for each statement in your proof, why it still holds. If it isn't,

find the first statement that is false (and explain why it is).

 

c) State a recurrence relation, including base case(s), for the number of times 3PASSSORT

compares two elements of A. Explain how each part of your recurrence links

to the algorithm.

 

d) State and prove upper and lower bounds for the solution to your recurrence. Your

bounds should be tight up to constant factors (and therefore expressible using

O, Ω, Θ notation).