Please type the answer out.

8. Consider the following list: 28, 18, 21, 10, 25, 30, 12, 71, 32, 58, 15 This list is to be sorted using the insertion sort algorithm. Show the resulting list after six passes of the sorting phase - that is, after six iterations of the for loop. 9. Perform the insertion sort algorithm using the following list of keys: 20, 32, 61, 22, 48, 75, 83, 35, 3 Show the list after each iteration. Exactly how many key comparisons are executed to sort this list using insertion sort? 18, 8, 11, 9, 15, 10. a. The performance of bubble sort can be improved if we stop the sorting process as soon as we find that in an iteration, no swapping of elements takes place. Write a function that implements bubble sort algorithm using this fact. b. Using the algorithm that you designed in part (a), find the number of iterations that are needed to sort the list: 65, 14, 52, 43, 75, 25, 80, 90, 95. 1. Suppose that L is a sorted list of 4096 elements. What is the maximum number of comparisons made by binary search to determine whether an item is in L? 2. Suppose that the elements of a list are in descending order, and they need to be put in ascending order. Write a C++ function that takes as input an array of items in descending order and the number of elements in the array. The function must not incorporate any sorting algorithms, that is, no item (key) comparisons should take place