1

I have homework assignment to implement merge sort in C++ via recursion. I'm not really good at recursion and what follows is the code I implemented, but it gives a stackoverflow error. Kindly tell me what I am doing wrong. EDITED VERSION

    #include<iostream>
using namespace std;
void divide(int A[], int n);
void sort();
int main(){
    int A[4]={2,3,0,5};
    divide(A, 4);
    for(int i =0 ;i<4;i++)
        cout<<A[i]<<endl;
    getchar();
}
void divide(int A[], int n){
    if(n<=2 && n>=1){
        for(int i=0; i<n; i++)
                if(A[i]>A[i+1]){

                int temp=A[i];
                A[i]= A[i+1];
                A[i+1]=temp;

                }
    }
    else{
    divide(A, n/2);
    divide(A,(n/2)+1 );
    }

}

In the code above, n is the number of elements to sort and A is the array I'm sorting.

Improve this question
7
  • 9
    What do you expect for divide(A, 3)? And, subsequently, divide(A, 1)? Commented Nov 28, 2014 at 15:00
  • or divide(A, 0) in other words). OK simply - this recursion never ends. Commented Nov 28, 2014 at 15:05
  • inside if clause I guess you are trying to do swapping which even looks wrong Commented Nov 28, 2014 at 15:11
  • 1
    This doesn't look very much like merge sort. The entire "merge" portion is missing. Plus the swap portion is wrong, the recursion termination condition is wrong, and the divide portion is wrong too (doing the same thing over the left portion of the array twice while not touching the right portion at all). Commented Nov 28, 2014 at 15:27
  • 1
    To understand the problem better you can also do this: take a deck of playing cards, take just one suit, shuffle it, and try to merge-sort it by hand. Commented Nov 28, 2014 at 15:45

3 Answers 3

Reset to default
1

Calling the below code with 

divide(A, 1);

Should illustrate the problem 

void divide(int A[], int n){
    if(n==2){ // first time n==1 so no, further calls are n==0 so also no.
        for(int i=0; i<2; i++)
            if(A[i]>A[i+1]){
                int temp=A[i];
                A[i]= A[i+1];
            }
    } else{
        divide(A, n/2); // for both n==1 and n== 0 => n==0, calls divide(A, 0)
        divide(A,(n/2)+1 ); // calls divide(A, 1) always 
    }
}

So the program will forever call divide(A, 0) until you run out of memory.

To stop this eternal recursion you need a correct stop condition

if (n<=2) {
    // correct code for swapping 1 or 2 elements
}  else

You could also check for incorrect values of n, which is 0, negative and larger than length of A.

Lets say you have A[]= {1,2,3} so you call 

divide(A, 3);

Now in the else part of the program you need to split up A in to parts, N/2 elements and the rest.

divide(A, n/2);

in our example this gives n/2 = 3/2 = 1 so

divide(A, 1);

and starting in the element just after the n/2'th element

divide(A+(n/2), n-(n/2));

the first element is at A[0], so the remaining start at A[1] and contains n-(n/2)=3-(3/2)=3-1=2 elements.

And now the first if, it looks like a bubble-sort, but fails as it address an element beyond the end of the array.

if(n<=2 && n>=1){
    for(int i=0; i<n; i++)
        if(A[i]>A[i+1]) {

A[i+1] is beyond the end of the array for i=1 and n=2, n=2 => 2 elements at address A[0] and A[1] so A[i+1]=A[2] which is not part of the array A with length 2.

    for(int i=0; i<n-1; i++)

solves that and also takes care of the case with n=1, which means the array contains only one element, which by definition is already sorted.

Now if the algorithm was called divide-sort you would be finished, but you still are missing the merge part.

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

5 Comments

thanks it did work for this input:[2,8,2,4,9,0,11] but not for this one [2,8,2,4,9,0,11]
These are the changes ive madde if(n<=2 && n>=1){ for(int i=0; i<n; i++) if(A[i]>A[i+1]){ int temp=A[i]; A[i]= A[i+1]; A[i+1]=temp; } } else{ divide(A, n/2); divide(A,(n/2)+1 ); }
Even though this improves the for loop, it is still wrong! consider both n=1 and n=2. Also the else part is wrong for a different reason, you always call with A, not the split range.
How shall I split it ?
Updated answer, you need to have learned how to use A+x for arrays to understand this.
1

You're still missing a merge. Merging is going to need a second temp array, I'll call it T and assume it's passed from main: 

void divide(int A[], int T[], int n){
    if(n < 2)
        return;
    if(n==2){
        // ... swap A[0], A[1] if needed (the existing code is ok)
        return;
    }
    divide(A, T, n/2);                   // recursively divide "left" half
    divide(A+(n/2), T+(n/2), n-(n/2));   // recursively divide "right" half
    merge(A, T, n/2, n)                  // merge the two halves
}
Improve this answer

Comments

1

It might be simpler to assume that a partition 0 or 1 element is already sorted. Thus, it is enough to put as stop condition

if (n < 2)
  return;
Improve this answer

Comments

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.