Shivesh Chandra - 1 year ago 91
C Question

# Merge Sort Program

``````#include<stdio.h>
#include<stdlib.h>

void merge(int a[],int l,int m,int r)
{
int i,j,k;
int n1= m - l + 1;
int n2= r - m;
int L[n1],R[n2];
for(i=0;i<n1;i++)
L[i]=a[l+i];
for(j=0;j<n2;j++)
R[j]=a[m + 1+ j];
i=0;j=0;k=l;
while(i<n1 && j<n2)
{
if(L[i]<R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
j++;
}
k++;
}
while(i<n1)
{
a[k]=L[i];
i++;
k++;
}
while(j<n2)
{
a[k]=R[j];
j++;
k++;
}
}

void mergeSort(int a[],int l,int r)
{
if(l<r)
{
int m = l+(r-1)/2;
mergeSort(a,l,m);
mergeSort(a,m+1,r);
merge(a,l,m,r);
}
}

void printArray(int a[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d   ",a[i]);
printf("\n");
}

int main()
{
int a[]= {
12,76,34,45,63,98
};
int n = sizeof(a)/sizeof(a[0]);
printf("The element entered in array   ");
printArray(a,n);
mergeSort(a,0,n-1);
printf("The element after sorting    ");
printArray(a,n);
return 0;
}
``````

This is a merge sort program.
Why it's giving runtime error if anyone can explain?
There is no error in this program
I have tried this 10 times.
And unable to find the solution.
Plz if anyone can help me on this.

When you call `mergesort(a, 3, 5)` the following happens:

``````int m = l+(r-1)/2;  // 3 + (5-1)/2 -> 3 + 4/2 -> 3 + 2 -> 5
mergeSort(a,l,m);   // So this will call: mergesort(a, 3, 5) again
``````

In other words: An endless loop.

``````int m = (l+(r-1))/2;

^       ^
notice
``````

So how did I find the bug?

Very easy - just use some printf-debug.

First I added a print in the start of `mergesort` - like:

``````void mergeSort(int a[],int l,int r)
{
printf("mergesort %d %d\n", l, r);  // Debug print
if(l<r)
{
int m = (l+(r-1))/2;
mergeSort(a,l,m);
mergeSort(a,m+1,r);
merge(a,l,m,r);
}
}
``````

and got the output:

``````mergesort 3 5
mergesort 3 5
mergesort 3 5
...
...
``````

which told me that there was an endless loop for input values 3 and 5.

Then I added a print of `m`

``````void mergeSort(int a[],int l,int r)
{
printf("mergesort %d %d\n", l, r);
if(l<r)
{
int m = (l+(r-1))/2;
printf("m %d\n", m);
mergeSort(a,l,m);
mergeSort(a,m+1,r);
merge(a,l,m,r);
}
}
``````

and got the output:

``````mergesort 3 5
m 5
mergesort 3 5
m 5
mergesort 3 5
m 5
``````

so obviously `m` was calculated wrongly.

Looking close at

``````int m = l+(r-1)/2;
``````

is was clear that the addition should be before the division. A set of `(....)` was missing.

Hope you can use this debug example for your own debug.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download