Skedbooks
←
Design Analysis of Algorithm

The Divide-and-conquer Approach

We must show that this loop invariant holds prior to the first iteration of the for loop of lines 12-17, that each iteration of the loop maintains the invariant, and that the invariant provides a useful property to show correctness when the loop terminates.

  • 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.

To see that the MERGE procedure runs in Θ(n) time, where n = r - p 1, observe that each of lines 1-3 and 8-11 takes constant time, the for loops of lines 4-7 take Θ(n1 n2) = Θ(n) time, and there are n iterations of the for loop of lines 12-17, each of which takes constant time.

We can now use the MERGE procedure as a subroutine in the merge sort algorithm. The procedure MERGE-SORT(A, p, r) sorts the elements in the subarray A[p ߩ r]. If p ≥ r, the subarray has at most one element and is therefore already sorted. Otherwise, the divide step simply computes an index q that partitions A[p ‥ r] into two subarrays: A[p ‥ q], containing ⌈n/2⌉ elements, and A[q 1 ‥ r], containing ⌊n/2⌋ elements.

MERGE-SORT(A, p, r)

1.      if p < r

2.         then q ← ⌊(p r)/2⌋

3.              MERGE-SORT(A, p, q)

4.              MERGE-SORT(A, q 1, r)

5.              MERGE(A, p, q, r)

To sort the entire sequence A = 〈A[1], A[2], . . . , A[n]〉, we make the initial call MERGE-SORT(A, 1, length[A]), where once again length[A] = n. Figure 2.4 illustrates the operation of the procedure bottom-up when n is a power of 2. The algorithm consists of merging pairs of 1-item sequences to form sorted sequences of length 2, merging pairs of sequences of length 2 to form sorted sequences of length 4, and so on, until two sequences of length n/2 are merged to form the final sorted sequence of length n.

Figure 2.4: The operation of merge sort on the array A = 〈5, 2, 4, 7, 1, 3, 2, 6〉. The lengths of the sorted sequences being merged increase as the algorithm progresses from bottom to top.