1. Consider the following well-known sorting algorithm, which is studied later in the book, with a counter inserted to count the number of key comparisons. ALGORITHM SortAnalysis(A[0..n 1]) //Input: An array A[0..n 1] of n orderable elements //Output: The total number of key comparisons made count 0 for i 1 to n 1 do

v A[i] j i 1 while j 0 and A[j ]> v do count count + 1 A[j + 1]A[j ] j j 1 A[j + 1]v return count Is the comparison counter inserted in the right place? If you believe it is, prove it; if you believe it is not, make an appropriate correction.

Run the program of Problem 1, with a properly inserted counter (or counters) for the number of key comparisons, on 20 random arrays of sizes 1000, 2000, 3000, . . . , 20,000. b. Analyze the data obtained to form a hypothesis about the algorithms average-case efficiency. c. Estimate the number of key comparisons we should expect for a randomly generated array of size 25,000 sorted by the same algorithm.

please provide the solution step by step