Action disvalue

Initialization: Prior to the first iteration of the loop, we have k = p, so that the subarray A[p..K-1]is empty. This empty subarray contains the k – p = 0 smallest elements of L and R, and since i = j = 1, both L[i] and R[j] are the smallest elements of their arrays that have not been copied back into A. Maintenance: To see that each iteration maintains the loop invariant, let us first suppose that L[i] <= R[j]. Then L[i] is the smallest element not yet copied back into A. Because A[p..K-1]contains the k - p smallest elements, after line 14 copies L[i]into A[k], the subarray A[p..K] will contain the k – p + 1 smallest elements. Incrementing k (in the for loop update) and i (in line 15) reestablishes the loop invariant for the next iteration. If instead L[i]> R[j], then lines 16–17 perform the appropriate action to maintain the loop invariant. Termination: At termination, k = r + 1. By the loop invariant, the subarray A[p..K-1], which is A[p..R], contains the k - p = r - p + 1 smallest elements of L[1.. N1+1] and R[1.. N2+1], in sorted order. The arrays L and R together contain n1 + n2 + 2 = r - p + 3 elements. All but the two largest have been copied back into A, and these two largest elements are the sentinels.