Issue with Merge Sort - Implementation in C++

Question

I am following the Merge Sort algorithm suggested in 2.3.1 of Introduction to Algorithms by Cormen. However, I am not getting the correct output. I am sure there's some silly mistake in here, but I haven't been able to figure that out for some time now. Any help would be really appreciated.

e.g: For input : 5,4,3,2,1, my output is 3 1 2 4 5 instead of 1 2 3 4 5.

Assume that the code will be tested for really small numbers, and that replacing the sentinel value ∞ (in the algorithm) by 999 does not affect the program.

Here is the code and the corresponding steps of the algorithm is in comments. An execution of this is here.

#include <iostream>
using namespace std;

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

    int i,j,k;
    int *L=new int[n1+1], *R = new int[n2+1];   //   3. let L[1...n1+1] and R[1..n2+1] be new arrays

    for(i=0; i<n1; i++)                         //   4. for i = 1 to n1
        L[i]=A[p+i];                            //   5.    L[i] = A[p+i-1]
       //the modification in above line is deliberately done to avoid IndexOutOfBounds when p=i=0 and is not because I forgot to subtract 1               
    for(j=0; j<n2;j++)                          //   6. for j = 1 to n2
        R[j]=A[q+j];                            //   7.    R[j] = A[q+j]

    L[n1]=999; //sentinel                       //   8. L[n1+1]= ∞
    R[n2]=999; //sentinel                       //   9. R[n2+1]= ∞
    i=0;                                        //  10. i = 1
    j=0;                                        //  11. j = 1
    for(k=p; k<r; k++) {                        //  12. for k = p to r 
        if(L[i]<=R[j])                          //  13.    if(L[i]<=R[j])
            A[k]=L[i++];                        //  14.         A[k] = L[i]
                                                //  15.         i = i+1
        else                                    //  16.    else A[k] = R[j]
            A[k]=R[j++];                        //  17.         j = j+1                 
    }

    delete(L);
    delete(R);
}

void mergeSort(int* a, int p, int r) {        // MERGE-SORT (A,p,r)
    if(p<r) {                                 //  1. if p<r 
        int q=(p+r)/2;                        //  2.   q = (p+r)/2 
        mergeSort(a,p,q);                     //  3.   MERGE-SORT(A,p,q)
        mergeSort(a,q+1,r);                   //  4.   MERGE-SORT(A,q+1,r)
        merge(a,p,q,r);                       //  5.   MERGE(A,p,q,r)
    }
}

int main() {
    int arr[]={5,4,3,2,1};
    mergeSort(arr,0,5);

    for(int i=0; i<5; i++)
        cout << arr[i]<<" ";
}

Answer 1

Your recursive calls to mergeSort suggest that p and r are the indices of the first and last item of a subarray to be sorted:

void mergeSort(int* a, int p, int r) {
    if(p<r) {
        int q=(p+r)/2;
        mergeSort(a,p,q);
        mergeSort(a,q+1,r);
        merge(a,p,q,r);
    }
}

If so, your call in main is incorrect:

int arr[]={5,4,3,2,1};
mergeSort(arr,0,5);

should be

int arr[]={5,4,3,2,1};
mergeSort(arr,0,4);

Next, copying the second half is wrong:

R[j]=A[q+j];

should be:

R[j]=A[q+1+j];

Note that p is an index of the first item in the left half, while q is an index of the last item of the left half – so the first item of the right half has index q+1, and that should be taken as a base for +j.

Finally,

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

should read

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

– r is an index of the last item in the right part, so you need to fill the [r] position of the merged subarray.

EDIT
See my answer to Sorting of an array using merge sort.

Answer 2

L[i]=A[p+i];                            //   5.    L[i] = A[p+i-1]

I think this is your problem, you do not follow the algorithm here, by fixing it a little (not using -1 because you start at 0) but in the next loop, you don't +1 when you're also not starting at the same number in the algorithm?

R[j]=A[q+j];                            //   7.    R[j] = A[q+j]

In the previous loop, you manually correct for starting at 0, instead of 1, but here you do not.