Merge sort using sentinels
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.