0

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]<<" ";
}
Improve this question
8
  • 1
    "However, I am not getting the correct output." What output are you getting? What's the expected output? Please provide a Minimal, Complete, Verifiable Example Commented Jun 10, 2015 at 19:10
  • I have added the ideone link for people to see. But for completeness, I'll edit it still. :) Commented Jun 10, 2015 at 19:11
  • 1
    Also... you don't want to be able to sort numbers larger than 999? Commented Jun 10, 2015 at 19:12
  • No. only for small numbers. If required, I can always change the sentinel to the maximum possible integer by calling the library functions. But for now, I just want to sort small numbers. Commented Jun 10, 2015 at 19:14
  • 2
    @Cheersandhth.-Alf, I was just trying to understand the algorithm, so used an integer array. I am not really implementing any big stuff right now. Otherwise, library calls are really efficient when compared to this. Commented Jun 10, 2015 at 19:22

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1 
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.

Improve this answer

7 Comments

Changing R[j] = A[q+j+1]. When j=n2-1, it would mean A[q+n2] = A[q+r-q] = A[r]. For r=5 (my initial call), this means an OutOfBounds.
@Anindya Dutta It seems correcting for one loop and not for another makes the code inconsistent with the source algorithm no? why don't you just keep the initial values at 1, and change the conditionals from '<' to '<=' so that you can be sure to stay consistent with the algorithm?
Yeah, I'll try by considering all the arrays from indices [1...n]. Seems a waste of the 0th index though. :\
Haha, yea it does. But hardcoding a fix to one loop, while leaving the other intact (which makes your algorithm different from the original) might cause problems with the logic.
Indeed, changing R[j]=A[q+j+1] did do the work. Thank you. I'm sorry about the part where I mentioned it going outOfBounds.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.