‘Advanced’ Recursive Functions - Sorting

See the Quicksort Code and the Mergesort Code here.

Questions:

1. What order is Mergesort in Big-Oh notation?

2. What order is Quicksort in Big-Oh notation?

3. Which is faster, Mergesort or Quicksort?

4. If we are trying to find the number 4 in the following array: 0 1 2 3 4 5 6 7 8 9, how many elements  would we compare to 4 before we found it? Which elements would be compared?

5. Trace the sorting of these numbers using Mergesort: 3 8 1 9 0 2 7 4

6. Trace the sorting of these numbers using Quicksort: 70 4 2 66 12 0 –21 6 3 57

7. Trace Quicksort when it is used on the following set of values: a, s, d, f, g, h, j, k, l, q, w, e, r.

8. Consider the following array of values: Q, W, E, R, T, Y, U, I, O, P.

(a) If Mergesort were used on this array, where would the first division occur?

(b) What would the array look like before the last call to Mergesort?