SORTING ALGORITHM: QUICKSORT

(a) Suppose we have a version of quick sort which selects pivots using the median-of-three strategy and creates partitions in the manner described in lecture. Explain how you would build an input array that would cause this version of quick sort to run in O (n2) time. Your answer should explain on a high level what your array would look like and what happens when you try running quick sort on it. You do not need to give a specific example of such a array, though you may if you think it will help make your explanation more clear. (b) Recall that merge sort works by taking an array, splitting it into two pieces, recursively sorting both pieces, then combining both pieces in O (n) time. Suppose that instead we split the array into three equally sized pieces instead of two. After we finish recursing on each of the three pieces, we merge two of the three pieces together, then merge that with the third piece to get the final sorted result. What is the worst-case asymptotic runtime of this variation on merge sort? Is it better or worse then the original version of merge sort? Be sure to justify your answers. (a) Suppose we have a version of quick sort which selects pivots using the median-of-three strategy and creates partitions in the manner described in lecture. Explain how you would build an input array that would cause this version of quick sort to run in O (n2) time. Your answer should explain on a high level what your array would look like and what happens when you try running quick sort on it. You do not need to give a specific example of such a array, though you may if you think it will help make your explanation more clear. (b) Recall that merge sort works by taking an array, splitting it into two pieces, recursively sorting both pieces, then combining both pieces in O (n) time. Suppose that instead we split the array into three equally sized pieces instead of two. After we finish recursing on each of the three pieces, we merge two of the three pieces together, then merge that with the third piece to get the final sorted result. What is the worst-case asymptotic runtime of this variation on merge sort? Is it better or worse then the original version of merge sort? Be sure to justify your answers