race insertion sort on the list $\{9,1,5,4,7,2\}$ i$.$e$.$ show what the list looks like after each iteration of the

outer loop. Also, calculate the exact number of total data comparisons made and number of total successful

insert operations made. Note that a data comparison is when two different pieces of data are compared,

and not when loop variables etc are compared.

$($b$)$ Trace the merge algorithm $($not the complete merge sort$)$ on the two lists $\{4,9,11,14\}$ and $\{2,7,16,20\}.$

Show what the combined list $($i$.$e$.$ the merged list$)$ looks like after every step and also calculate the exact

number of total data comparisons made.

$($c$)$ Trace the mergesort algorithm on the list $\{9,1,5,4,7,2\}.$ Show what the list looks like after every step and

calculate the exact number of total data comparisons and successful swaps made. You may build a tree

and number the order of the recursive calls as seen in class for tracing if you prefer.