Please translate the following Merge Sort PseudoCode to C++ Code: CONFUSION: How
ID: 3787325 • Letter: P
Question
Please translate the following Merge Sort PseudoCode to C++ Code:
CONFUSION: How to initalize "Let L[1...n1+1] and R[1...n2+1] be new arrays" in the function MERGE.
Is it Merge(L[], R[], p , q, r) or do I have to initalize the array inside the function, i.e, int *L[] = new int []; ?
MERGE(A,p,q,r)
n1 = q-p+1
n2 = r-q
Let L[1...n1+1] and R[1...n2+1] be new arrays
for i = 1 to n1
L[i] = A[p+i-1]
for j = 1 to n2
R[j] = A[q+j]
L[n1+1] = SENTINEL
R[n2+1] = SENTINEL
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
Explanation / Answer
// C++ code merge sort
void merge(int A[], int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
// declare the temporary arrays
int L[n1+1], R[n2+1];
// copy data from main array to temporary arrays L and R
for (i = 1; i <= n1; i++)
L[i] = A[p + i - 1];
for (j = 1; j <= n2; j++)
R[j] = A[q + j];
/* Merge the temp arrays back into A[p..r]*/
i = 1; // Initial index of first subarray
j = 1; // Initial index of second subarray
// merge arrays in A
for( k = p; k <= r; k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
}
}