I have a buffer overflow problem while writing mergesort() in C++

Question

The prompt question is, the size of the help array that can be written is (R-L+1)*'4' bytes, but '8' bytes may be written, what does this mean?Is the array out of bounds, but I think it is logically correct, the specific code is as follows：

void merge(int a[], int L, int M, int R) {
    int* help = new int[R - L + 1];
    int i = 0;
    int p = L;
    int q = M + 1;
    while (p <= M && q <= R) {
        help[i++] = a[p] <= a[q] ? a[p++] : a[q++];
    }
    while (p <= M) {
        help[i++] = a[i++];
    }
    while (q <= R) {

        help[i++] = a[i++];
    }
    for (i = 0; i < R - L + 1; i++) {
        a[L + i] = help[i];
    }

}

Answer 1

Your merge is hitting an infinite loop because both 'finishing' loops are broken.

void merge(int a[], int L, int M, int R)
{
    int *help = new int[R - L + 1];
    int i = 0;
    int p = L;
    int q = M + 1;
    while (p <= M && q <= R)
    {
        help[i++] = a[p] <= a[q] ? a[p++] : a[q++];
    }

    while (p <= M)
    {
        help[i++] = a[i++];  // THIS IS WRONG
    }

    while (q <= R)
    {
        help[i++] = a[i++];  // THIS IS WRONG
    }

    for (i = 0; i < R - L + 1; i++)
    {
        a[L + i] = help[i];
    }
}

In both cases, the predicate of the loop control, (p in the first case, q in the second), is never modified. So you just keep marching up a double post-incrementing i along the way.

Fixing both is relatively easy, but you can also just get rid of the second while loop entirely and base your final copy-back loop on a cap of i. If the left sub-segment finished early, the right side remaining is already in place at the high side of a[], so there's not reason to copy it over, just to copy it back.

void merge(int a[], int L, int M, int R)
{
    int *help = new int[R - L + 1];
    int i = 0;
    int p = L;
    int q = M + 1;

    while (p <= M && q <= R)
    {
        help[i++] = a[p] <= a[q] ? a[p++] : a[q++];
    }

    while (p <= M)
    {
        help[i++] = a[p++];
    }

    for (int j = 0; j<i; ++j)
    {
        a[L+j] = help[j];
    }

    delete [] help;
}