We can express insertion sort as a recursive procedure as follows. In order to sort A[1 ...n], we recursively sort A[1 ... n-1) and then insert A[n] into the sorted array A[1 ... n_1]. First, write a recurrence for the running time of the recursive version of insertion sont given below. Then find the running time by solving the recurrence. Insertion-Sort-Recursive (int[] A, int n) {
if(n== 0) return;
// recursively sort A[1... n-1] Insertion-Sort-Recursive (A, n-1);
int key = A[n];
// insert A[n] into the sorted array A[1 ... n_1].
for (int j =n-1;G>0) && (AG] >key); j--) A[i+1] = [j]; A[i+1] = key;