5. Sorting Lower Bounds. (5 points) In class, we derived a lower bound for comparison- based sorting algorithms using decision trees. We illustrated the decision tree for sorting 3 distinct elements using insertion sort. Draw the decision tree for (worst-case) deterministic quicksort and indicate the contents of the array on each edge of the path that was taken in the tree 6. Linear-Time Sorting. In this question, we will look at how to use the linear-sorting algorithms that we studied in class. (a) (5 points) Show how to sort n integers in the range nn O(n) time (b) Bonus 5 points) Describe an algorithm (using pseudocode that takes a input n integers in the range between 0 and k and an itevai,j then outputs the number of integers that are in between i and j (inclusive). The algorithm should run in time (n +k)