Part (A) Sort the array 15 80 35 25 60 30 into descending order using
a) the selection sort.
b) the buble sort.
Part (B) A first year student attempted to write mergesort in pseudocode as follows.
mergesort(theArray, n) {
if (n > 1){ // more than one item to sort
mergesort(left half of theArray, n/2)
mergesort(right half of theArray, n/2)
}
}
a) The above algorithm has a fundamental flaw. As written, how does it change theArray?
b) What is the worst-case runtime of this incorrect algorithm? Give as tight an asymptotic upper bound as possible, using Big-Oh notation as a function of n. Justify your answer.
The original course website where the problem comes from is here, I think it will be helpful if you take a look at it first: www.student.math.uwaterloo.ca/~cs134