Issue with Merge Sort implementation in C++

Question

I am getting two errors in implementing the algorithm from pseudocode:

One of my problems is int L[n1+1]; error: needs to be a constant; cannot allocate constant size 0. The only way to run this is to make the size a number like 10. I may be implementing the psuedocode wrong that is why I included the statement above that. This may be the cause of my next problem.

My other problem is I am printing only one line of code unsorted. My print function is flawless and works for all of the sorting programs. I believe the MERGE function is only running once. I posted the output of the Sort at the bottom.

I have a random number generator for the array A, from 0 to RAND_MAX. Initial call is MERGESORT(A,1,n);

void MERGE(int *A, int p, int q, int r)
{
    int n1 = q-(p+1);
    int n2 = r-q;

  //psuedocode states, let L[1..n1+1] & R[1..n1+1] be new arrays

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

    for(int i=1; i<n1;i++)
    {
        L[i]=A[p+(i-1)];
    }
    for(int j=1; j<n2; j++)
    {
        R[j] = A[q+j];
    }
    L[n1+1]=NULL; //sentinel
    R[n2+1]=NULL; //sentinel
    int i=1;
    int j=1;
    for (int k=p; k<r; k++)
    {
        if(L[i]<=R[j])
        {
            A[k]=L[i];
            i=i+1;
        }
        else
        {
            A[k]=R[j];
            j=j+1;
        }
    }
}

void MERGESORT(int *A,int p, int r)
{
    if (p<r)
    {
        int q=floor((p+r)/2);
        MERGESORT(A,p,q);
        MERGESORT(A,q+1,r);
        MERGE(A,p,q,r);
    }
}

With int L[10]; and my A[10]; my output is:

Sort:  7474 28268 32506 13774 14411
Press any key to continue . . .

If someone could just assist in the two problems, I more than likely will get it to work.

Answer 1

There are several issues with your code, I've pointed them out in comments. This is a solution closest to your code, and it's far from best. Consider using C++ containers, like std::vector for example. Naming is at least disputable, and of course merge sort should be implemented as an in place algorithm.

//L and R are auxiliary arrays 
//preallocated with (inputSize/2 + 1) constant size
void MERGE(int *A, int p, int q, int r, int* L, int* R)
{
    if (p > q || q > r)
    {
        return;
    }

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

    // note 0-based indices
    int i = 0;
    int j = 0;

    for(;i < n1;i++)
    {
        L[i] = A[p + i];
    }

    for(;j < n2;j++)
    {
        R[j] = A[q + j + 1];  //+1 because p + n1 - 1 == q + 0
    }

    //again - note 0-based indices
    i = 0;
    j = 0;

    for (int k = p; k <= r; ++k)
    {
        // The most important fix - in your code you didn't check
        // for left/right array bounds at all.
        // Sentinel values aren't needed - size is known
        if(i < n1 && (j >= n2 || L[i] <= R[j]))
        {
            A[k] = L[i];
            ++i;
        }
        else if (j < n2)
        {
            A[k] = R[j];
            ++j;
        }
    }
}

void MERGESORT(int* A, int p, int r, int* L, int* R)
{
    if (p < r)
    {
        int q = (p + r) / 2;  //floor was redundant
        MERGESORT(A, p, q, L, R);
        MERGESORT(A, q+1, r, L, R);

        MERGE(A, p, q, r, L, R);
    }
}

void MERGESORT(int* A, int size)
{
    int*L = new int[size/2 + 1]; //preallocate auxiliary arrays
    int*R = new int[size/2 + 1]; //size/2 + 1 is what will be needed at most

    MERGESORT(A, 0, size - 1, L, R);

    delete L;
    delete R;
}

int main()
{
    int A[5]{ 7474, 28268, 32506, 13774, 14411 };

    MERGESORT(A, 5);

    for (int i = 0;i < 5;++i)
    {
        std::cout << A[i] << std::endl;
    }

    return 0;
}

Output:

7474
13774
14411
28268
32506

Credit goes also to DyP for spotting all the mistakes in the previous version :)

Answer 2

You are failing to detect the end of your merge arrays:

for (int k=p; k<r; k++)
{

    // You need to check that i/j are still in range.
    // otherwise the following test are not valid.

    if ((i < n1) && (j < n2))
    {
      if(L[i]<=R[j])
      {
        A[k]=L[i];
        i=i+1;
      }
      else 
      {
        A[k]=R[j];
        j=j+1;
      }
    }
    else
    {   /* More work here */
    }

Other comments:

Identifiers that are all capitol MERGE MERGESORT are generally reserved for macros. If you use them you are likely to hit problems. Prefer function names of mixed case.

You can simulate arrays with vector:

// Simulate L[1..n1+1]
minI = 1;
maxI = n1-1;
std::vector<int> const L(A+(minI-1), A+(maxI-1));     

Arrays in C++ are zero indexed. You seem to be having off by one errors (especially in accessing the end of the array). I would advice you to start the count at 0 rather than 1. Most C++ code is written in terms of iterators from [begining..1PastEnd). I think you will find your algorithm easier to implement if you adapt that style.