# Exercise 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.

Here is a simple modification:

MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1..n₁] and R[1..n₂] be new arrays
for i = 1 to n₁
L[i] = A[p + i - 1]
for j = 1 to n₂
R[j] = A[q + j]
i = 1
j = 1
for k = p to r
if i > n₁
A[k] = R[j]
j = j + 1
else if j > n₂
A[k] = L[i]
i = i + 1
else if L[i] ≤ R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1


### C code

#include <stdio.h>

void merge(int A[], int p, int q, int r) {
int i, j, k;

int n1 = q - p + 1;
int n2 = r - q;

int L[n1];
int R[n2];

for (i = 0; i < n1; i++)
L[i] = A[p + i];
for (j = 0; j < n2; j++)
R[j] = A[q + j + 1];

for(i = 0, j = 0, k = p; k <= r; k++) {
if (i == n1) {
A[k] = R[j++];
} else if (j == n2) {
A[k] = L[i++];
} else if (L[i] <= R[j]) {
A[k] = L[i++];
} else {
A[k] = R[j++];
}
}
}

void merge_sort(int A[], int p, int r) {
if (p < r) {
int q = (p + r) / 2;
merge_sort(A, p, q);
merge_sort(A, q + 1, r);
merge(A, p, q, r);
}
}