Merge Sort in C++

Question

I've written this code for a merge sort, which is meant to implement the pseudo-code from Cormen's Introduction to Algorithms:

#include <iostream>
#include <cstdlib>

using namespace std;

const unsigned long long infinity = -1ULL;

void merge(int* A,int p,const int q, const int r)
{
    const int n_1=q-p+1;
    const int n_2=r-q;
    int* L = new int [n_1+1];
    int* R = new int [n_2+1];
    L[n_1]=infinity;
    R[n_2]=infinity;
    for(int i = 0; i < n_1; i++) 
        L[i] = A[p+i];
    for (int j = 0; j < n_2; j++)
        R[j] = A[q+j+1];

    int i=0;
    int j=0;
    // for(int k = p; k <= r; p++)   broken code
    int k;
    for(k=p; k <= r && i < n_1 && j < n_2; ++k)
    {
        if(L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;        
        }
    }
    // Added the following two loop.
    // Note only zero or one loop will actually activate.
    while (i < n_1) {A[k++] = L[i++];}
    while (j < n_2) {A[k++] = R[j++];}
}     

void merge_sort(int* A, const int p, const 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);
    }
}

int main()
{
    int length;
    cout << "Specify array length" << endl;
    cin >> length;
    cout << "\n";

    int A [length];

    //Populate and print the Array
    for(int i = 0; i < length; i++)
    {
         A[i] = rand()%99-1;
                 cout << A[i] << " ";
    }    

    cout << "\n";
    merge_sort(A,0,length-1);
    cout << "Your array has been merge_sorted and is now this: " <<         endl;
    for(int i = 0; i < length; i++) cout << A[i] << " ";

    cout << "\n";
    //cout << infinity << endl;
    return 0;
}

Answer 1

Don't do this:

using namespace std;

For a detailed explanation on why not to use the usign clause.

This is not used anywhere (also its not infinity so baddy named).

const unsigned long long infinity = -1ULL;

Passing pointers is a not a good idea.

void merge(int* A,int p,const int q, const int r)

Try and avoid it because you get into the realm of ownership symantics. Here I would be OK with using it but I would definitely rename the variable to explain what it is. You have a tendency to use excessively short variable names; this make the code hard to read.

If you use the standard practive of begin and end (used in the STL (so begin points at the first and end points one past the last)) then you will find that your code becomes a lot simpler to write (especially in this case).

    const int n_1=q-p+1;
    const int n_2=r-q;

This is stupendously bad for C++ code. This looks like C code.

    int* L = new int [n_1+1];
    int* R = new int [n_2+1];

You should practically never use new. When you do you should always match it with delete (I see no delete anywhere so your code leaks). The reason you never use new is the problem with matching it with delete (especially when exceptions can be flying around). What you want to do is use a container:

    std::vector<int>  left(n_1+1);
    std::vector<int>  right(n_2+1);

You only use new and delete when building your own container types or in very low level code. Normally you will use existing containers std::vector or smart pointers (for these use make_{smartpointertype}.

Has no affect:

    L[n_1]=infinity;
    R[n_2]=infinity;

Especially since you never check for infinity. Also because you always know the exect bounds and should not fall off the end.

Also this is a particularly bad implementation of the algorithm.
Most version I have seen use a split/merge in place algorithm. Thus you don't need to copy data around into new arrays all over the place.

    for(int i = 0; i < n_1; i++) 
        L[i] = A[p+i];
    for (int j = 0; j < n_2; j++)
        R[j] = A[q+j+1];


    for(k=p; k <= r && i < n_1 && j < n_2; ++k)
    {
        if(L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;        
        }
    }