Below is the MERGE procedure from the Merge sort algorithm: MERGE(A, p, g, r) n_1 = q-p+1 n_2 = r-q let L [1..n_1+1]and R[1..n_2+1] be new arrays for I = 1 to n_1 L[i] = A[p+i-1] for j = 1 to n_2 R[j]=A[q+j] L[n_1+1] = infinity R[n_2+1] = infinity i=1 j=1 for k = p to r if L[i] lessthanorequalto R[j] A[k] = L[i] i = i+1 else A[k] = R[j] j = j+1 Which of the following is the correct loop invariant for the for loop in lines 12.17? At the start of each iteration k of the for loop, the subarray A[p..k-1] contains the (k-p) smallest elements of A [p..r] in sorted order. At the start of each iteration i of the for loop, the subarray A[p..r] contains the (i-p) smallest elements of A[p..r] in sorted order. At the start of each iteration k of the for loop, the subarray A[1..k] contains the k smallest elements of A in sorted order. At the start of each iteration k of the for loop, the subarray A[k..r] contains the (r-k+1) largest elements of A[p..r] in sorted order