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.

• recursion.ninja: Don't ever use l as a single letter variable name, it is notoriously difficult to distinguish from 1.

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.

• SouvikMaji: merge is a called recursively several times. Where and when should i free those.
• 200_success: l and m are just temporary storage space for doing merge(). After you're done merging the contents of l and m back into a, you should free l and m.

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.

• Voo: There's also the longer version of the quote that goes: There are only two hard things in Computer Science: cache invalidation, naming things and off by one errors. :-)
• Morwenn: @Voo Yeah, I also love that one :D