Error in merge sort program

Question

I am doing a merge sort program in C but I'm getting some unexpected output. Can anyone find out error in the program?

   #include<stdio.h>

    int array[100],n;
    void merge(int l,int m,int h);
    void mergesort(int start,int end);
    main(){
    int i;
    printf("Enter Size: ");
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&array[i]);      
    }
    mergesort(0, n-1);
    for(i=0;i<n;i++){
        printf("%d\n",array[i]);        
        }
    }

    void mergesort(int start,int end){
    int mid;
    if(start<end){
        mid=(start+end)/2;
        mergesort(start,mid);
        mergesort(mid+1,end);
        merge(start,mid,end);
        }
     }

    void merge(int start,int mid,int end){
    int i,j,k;
    int a1[100],a2[100];

    for(k=0,i=start;i<=mid;i++,k++){
        a1[k]=array[i];
    }
    for(k=0,j=i;j<=end;j++,k++){
        a2[k]=array[j]; 
    }
    a1[mid]=999;
    a2[j]=999;
    i=0;j=0;
    for(k=start; k <=end; k++)
    {
        if(a1[i]<=a2[j])
            array[k]=a1[i++];
        else
            array[k]=a2[j++];
    }
}

Output:

Enter Size: 5
1 2 3 2 3
2
2
3
3
-1818025592

For larger arrays, the output is more scrambled. I think there is an error in merge() function.

Answer 1

I have solved it
a[mid + 1]=999
a[k]=999

Answer 2

When you create your temporary arrays:

for (k = 0, i = start; i <= mid; i++, k++) {
    a1[k] = array[i];
}
a1[i] = 999;

you put a sentinel value with a high value at the end. But i is the index into the original array. You must use k, the index of the temporary array a1:

for (k = 0, i = start; i <= mid; i++, k++) {
    a1[k] = array[i];
}
a1[k] = 999;

Even so, the double control structure with k and i is clumsy. And there's no need to guess a high number; <limits.h> has constants defined for the min and max values of most types:

k = 0;
for (i = start; i <= mid; i++) {
    a1[k++] = array[i];
}
a1[k] = INT_MAX;

Here, you increment k when an item is appended. This works even when the assignment happens conditionally, i.e. not in all iterations.

Finally, I would recommend to use exclusive upper bounds. That's the natural way to express ranges in C. mid would then be both the exclusive upper bound of the left array and the inclusive lower bound of the right array.

Answer 3

You are terminating your a1 and a2 arrays at the wrong location.

Try changing:

for(k=0,i=start;i<=mid;i++,k++){
    a1[k]=array[i];
}
for(k=0,j=i;j<=end;j++,k++){
    a2[k]=array[j]; 
}
a1[mid]=999;
a2[j]=999;

to

for(k=0,i=start;i<=mid;i++,k++){
    a1[k]=array[i];
}
a1[k]=999;
for(k=0,j=i;j<=end;j++,k++){
    a2[k]=array[j]; 
}
a2[k]=999;