Question is from algorithams analysis & design course
(a) Trace insertion sort on the list 7,5,1,4,2,6 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. Note that a data comparison is when two diﬀerent 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 1,5,7,14 and 2,4,8,11. 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.