Merge Sort : need of copying elements from temporary array

Question

I've been trying to analyse mergesort,but i got struck at a strange bug. this is my code:

int merge(int *a,int st,int mid,int en)
{
    int i,j,l,m;
    i = st;
    l = st;
    m = mid + 1;
    while((l<=mid) && (m <= en))
    {
        if(a[l] <= a[m])
        {
            temp[i] = a[l];
            l++;
            i++;
        }
        else
        {
            temp[i] = a[m];
            m++;
            i++;
        }
    }
    if(l <= mid)
    {
        for(j=l;j<=mid;j++)
        {
            temp[i] = a[j];
            i++;
        }
    }
    else 
    {
        for(j=m;j<=en;j++)
        {
            temp[i] = a[j];
            i++;
        }
    }
    for(j=st;j<=en;j++) // ??
        a[j] = temp[j];  // ??
}

void mergesort(int *a,int st,int en)
{
    int mid;
    if(st<en)
    {
        mid = (st+en)/2;
        mergesort(a,st,mid);
        mergesort(a,mid+1,en);
        merge(a,st,mid,en);
    }
}

int main()
{
    int i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    mergesort(a,0,n-1);
    for(i=0;i<n;i++)
        printf("%d\n",temp[i]);
    getch();
    return 0;
}

I've been using typical merge sort code.I'm facing problem to understand why is it necessary to copy the contents from temp array to main array to get the correct output.I tried this on following input: 5 (number of terms) ,
4 4 5 3 2

And I'm getting output as : 3 2 4 4 5 without copying the contents from temp array to main array and if I do the copying using the "commented" loop,the output is fine i.e. 2 3 4 4 5. I'm just not getting,why is this happening?

Answer 1

The copy is neccessary as the copying is done in the merge function not in the mergesort function.Merge function has to be called again and again recursively; so the temp array will keep on changing.

You need to put the partially sorted part of the original array in the original array in each mergesort call.That partially sorted part is actually the temp array.