Shivesh Chandra Shivesh Chandra - 2 months ago 17
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.

Answer

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.

Maybe you want this instead:

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.

Comments