Implementation of recursive Mergesort

Question

I made a recursive merge sort code,but it is not working,can anyone tell me where am I going wrong in the code.

void mergesort(int A[],int start,int end)
{
    int B[(end-start)/2],C[(end-start)/2],i,j,k,flag=0;
    if(start==end)
      return;
    else
    {
      mergesort(A,start,(start+end)/2);
      mergesort(A,(start+end)/2+1,end);
    }
    for(i=start;i<(start+end)/2;i++)
      B[i]=A[i];
    for(i=(start+end)/2+1;i<end;i++)
      C[i]=A[i];
    for(i=start,j=start,k=(start+end)/2+1;i<end;i++)
    {
        if(j==(start+end)/2)
        {
            while(k!=end)
              A[i]=C[k++];
            flag=1;
        }
        if(k==end)
        {
            while(j!=(start+end)/2)
              A[i]=B[j++];
            flag=1;
        }
        if(flag)
          break;
        if(A[j]&gt;C[k])
          A[i]=C[k++];
        else
          A[i]=B[j++];
    }
    return;
}

In the first part of the code i am trying to divide the array into 2 sub arrays and if i am left with only one element, I start merging and reach the top to obtain the sorted array.

Answer 1

One of the end points in your recursive calls is wrong. You need to decide if end is included in the sub-array or one past the end of the array. The code appears to want to exclude end, however your recursive calls look like this:

mergesort(A,start,(start+end)/2); // should be (start+end)/2+1 if end is excluded
mergesort(A,(start+end)/2+1,end);