Below is the MERGE procedure from the Merge sort algorithm: MERGE(A, p, g, r) n_

Question

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.

Explanation / Answer

The loop just copies(merges) the elements from two sorted arrays L and R into the array A.

So, the answer is:

At the start of each iteration k of the for loop, the subarray A[p..k-1] contains the k-p smallest elements of the A[p..r] in sorted order.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.