// index 0 1 2 3 4 5 6 7 8 t 16, 21, 45, 8, 11, 53, 3, 26, 49 Trace the execution of the selection sort algorithm over the array above. Show each pass of the algorithm and the state of the array after the pass has been performed, until the list is sorted. // index 0 1 2 3 4 5 6 7 8 Trace the execution of the insertion sort algorithm over the array above. Show each pass of the 16, 21, 45, 8, 11, 53, 3, 26, 49) algorithm and the state of the array after the pass has been performed, until the list is sorted. What are the best, average, and worst Big-Oh descriptions of selection sort and insertion sort? Merge Sort: Finish the merge sort code. Assume that you can call a merge function that takes 3 lists and will merge 2 of the lists into the other list. def merge_sort (list1): if len(list1) >1: md= len (list!) // 2 left half listi[ :mid] Quicksort: // index 0 1 2 3 4 5 6 7 8 16, 21, 45, 8, 11, 53, 3, 26, 49) Trace the execution of one pass (which does one partition) of the quick sort algorithm with the array above, using the Median of Three to choose the pivot. Chose the first element in the array as the pivot. What value would the best possible pivot? Explain why choosing the first element as the pivot is a poor design. When would this lead to poor performance? What would be the Big-Oh description of this poor performance