A) Show how in-place Quicksort would sort the following list of numbers: 8 3 1 9 6 2 4 5. First, show the swaps that would take place if the last element were chosen as the pivot. Then show the list after the two recursive calls.

B) Explain why QuickSort is still O(n lg n) expected time, even when it uses InsertionSort repeatedly to sort sub-lists of 15 or fewer items. Recall that InsertionSort is an (n²) algorithm.

C) What is a randomized algorithm? Explain why we might prefer an expected runtime of (n log n) for a randomized algorithm to an average-case runtime of (n log n) for a deterministic algorithm. (For example, why would we prefer Randomized QuickSort to Deterministic (non-randomized) QuickSort? But dont limit your answer to QuickSort.)