Draw the right half of the decision tree for Insertion Sort on an array of size n = 4. in other words, assume that the first comparison a_1: a_2, always satisfies a_1 > a_2. This problem has to do with stable sorting algorithms. Recall from the class that we claimed that counting sort is a stable sorting algorithm. Prove that counting sort is in fact stable. Is deterministic quicksort (i.e. when we always choose the first element to be the pivot) a stable sorting algorithm? Prove that it is stable or give an example for which it produces an unstable result. This problem has to do with the choice of a pivot in quicksort. Describe the property that the pivot must satisfy in order for quicksort to have its best-case running time. Explain how the order statistics algorithm described in class can be used to generate a good pivot. What is the worst-case running time of this algorithm? What is the expected running time of this algorithm