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?