Do question 1.

Problem 1. Use the Insertion Sort pseudocode to answer the following questions: INSERTION-SORT(A for j 2 to A.length times cost key = A[j] /Comment while i > 0 and A[ij> key C5 7 A. proof that insertion sort running time is O(n2) B. argue the running time of the while loop 2t; Problem 2. Illustrate a complete trace of a merge sort of the following array. Show all the arrays using a tree diagram, how can you prove MERGE sort runs in O(nlogn)