A problem about Sorting in Java

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