[Introduction to Algorithms, CLRS] Exercises 2.3-2

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.3-2

Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.

Answer:

MERGE(A, p, q, r)

1    n1 = q - p + 1

2   n2 = r - q

3    let L[1..n1 + 1] and R[1..n2 + 1] be new arrays 

4    for i = 1 to n1

5        L[i] = A[p + i - 1]

6    for j = 1 to n2

7        R[j] = A[q + j]

8    i = 1

9    j = 1

10    k = 1

11    for k = p to r

12        if L[i] <= R[j]

13            A[k] = L[i]

14            i = i +1

15        else A[k] = R[j]

16            j = j + 1 

17    if i <= n1    

18        while k <= r

19            A[k] = L[i]

20            i = i + 1

21    else while k <= r

22            A[k] = R[j]

23            j = j + 1