Merge sort using sentinels

Question

This is my implementation of recursive merge sort, using sentinels:

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

void merge(int a[], int p, int q, int r)
{
    int n1,n2;
    int i,j,k;
    int *l,*m;

    n1 = q - p + 1;
    n2 = r - q;
    l = (int*)malloc(sizeof(int)*(n1+1));
    m = (int*)malloc(sizeof(int)*(n2+1));

    for(i=0; i<n1; i++)
        l[i] = a[p+i];
    for(j=0; j<n2; j++)
            m[j] = a[q+j+1];
    l[i] = INT_MAX;
    m[j] = INT_MAX;

    i = j = 0;
    for(k=p; k<r+1; k++){

        if(l[i] <= m[j]){
            a[k] = l[i];
            i++;
        }

        else{
            a[k] = m[j];
            j++;
        }

    }
}

void merge_sort(int a[],int p, int r)
{
    int q;

    if(p<r){
        q = (p+r)/2;
        merge_sort(a,p,q);
        merge_sort(a,q+1,r);
        merge(a,p,q,r);
    }
}
int main()
{
    int *num,n;
    int i;

    printf("Enter number of digits:");
    scanf("%d",&n);
    num = (int*)malloc(sizeof(int)*n);
    printf("Enter numbers:");   
    for(i=0 ; i<n; i++){
        scanf("%d",&num[i]);
    }
    merge_sort(num,0,n-1);
    printf("Sorted array:\n");
    for(i=0; i<n; i++)
        printf("%d ",num[i]);
    free(num);
    return 0;
}

I'm looking for reviews, suggestions, and improvements.

Answer 1

In merge(), you call malloc() twice with no corresponding calls to free(). That can't be good for your memory consumption!

When computing the average of two values, don't do q = (p+r)/2, because that is vulnerable to overflow. Instead, write it as q = p + (r - p) / 2.

Answer 2

What strikes me most is your variables names: they are cryptic. Having short name for loop indices is ok, but you should at least name your function parameters so that anybody using your function knows what they are supposed to pass to it. When I read merge_sort, I know that I will have to pass a collection; here we have int a[] which without a doubt the array parameter. However, an array parameter decays to a pointer, so I also know that I will probably have to pass a size, but then we have two parameters p and r and I have no idea what they mean (from your main, we can infer their meaning, but a potential user doesn't always have a friendly main to explain how it works).

There is a famous quote concerning computer programming:

There are only two hard things in Computer Science: cache invalidation and naming things.

You should take some time to give meaningful names to your functions and to your variables (and structures, etc...) as much as you take time thinking about the programming logic itself. Meaningful names improve readability and maintainability of a code base.