CODEWITHSUNDEEP
c
user2989350
user2989350

Reputation: 1

Why is this code for implementing mergesort not producing correct result?

Here in I'm trying to implement mergesort on array of 10 elements. On providing the input a[10]={9,8,7,6,5,4,3,2,1,0} , I obtain the output as {0,0,1,1,0, 4,4,4,3,2} while the expected output is {0,1,2,3,4,5,6,7,8,9}. I am calling the mergesort in main with l=0,h=9. 

void mergesort(int a[],int l,int h)
    {   
      int c[10];
      int m=(l+h)/2;
      if(l<h)
      { 
            mergesort(a,l,m);           // Recursive call to sort first half
            mergesort(a,m+1,h);         // Recursive call to sort second half
        }
        int i,k=l,j=l;
        while(k<=h)                        // Merging the first and second half of the array
        {   
            if(a[j]<a[m+1])
            {
                c[k]=a[j];
                k++;
                j++;
            }
            else
            {
                c[k]=a[m+1];
                k++;
                m++;
            }       
        }
        for(i=l;i<=h;i++)
            a[i]=c[i];  
    }

Upvotes: 0

Views: 85

Answers (2)

Chris
Chris

Reputation: 27599

The problem is that in your while loop you are sometimes looking outside the bounds you should be.

Assuming you put in a check at the beginning of your function saying if l==h then return (since sorting a one element array is unnecessary) then the first time it will do anything is when it recurses to mergesort(a, 0,1). Here we are basically merging two single element arrays.

When going through your loop the first time we have i,j,k,m=0. We will go into the else part of the if because element 0 is greater than 1. We thus write out a[1] into the output array and we now have i,j=0 and k,m=1. What we now should do is note that our second array is exhausted and fill from the remaining elements in the first array.

Instead what we do is compare elements j and m+1 (ie 0 and 2). This is clearly wrong because element 2 shouldn't appear in the array. We of course find element 2 is smaller and thus put that into the output array at position two. Once we copy this over a we get {8, 7, 7, 6, 5, 4, 3, 2, 1, 0} and this is where it all goes wrong.

Upvotes: 1

benipalj
benipalj

Reputation: 704

One of the few problems: Your value of l is no longer a valid left limit after the while loop since you are incrementing it. So when you are copying from array c to a later in the for loop, you are copying invalid data.

Upvotes: 1

Related Questions