void msort(int *array,int start,int end)
{
 if start=end then return back;
 if end-start=1 implies there are only two elements swap if necessary n return;
 msort(array,start,(start+end)/2);
 msort(array,(start+end)/2,end);
/* at this point we have two sorted arrays one frm start to(start+end)/2 rest the other*/
 /*create a dummy array of required size merge the two sorted arrays by comparing cunterpart elements n swapping if necessary n store in this dummy array*/
 /*now make array point to dummy*/ 
  array = dummy;
  /*at every recursive step dummy is newly created that fits the whole size of the array (i.e frm start to end) n so this shud not create a memory conflict as dummy is local to each function*/
 /* when everything is done array is sorted*/
}

	#include"stdio.h"
	#include"malloc.h"
	#include"stdlib.h"

	void msort(int *,int,int);

 main()
{
 int *arr,n,i;
 int start,end;
 printf("Input n (no. of elements in the array) : "); //n is size of array
 scanf("%d",&n);
 arr = (int *)malloc(4*n);
 for(i=0;i<n;i++)
    scanf("%d",arr+i);
 msort(arr,0,n-1);   //passing the entire arry with start=0 end=n-1
}

 void msort(int *p,int start,int end)
{
 int temp,i,mid=(start+end)/2,j;
 int *q=(int *)malloc(4*((end-start)+1)),*dummy;
 printf("Entered msort with start=%d end=%d\n",start,end);
 if(!q)
 {
   printf("failure allocating memory\n");
	exit(0);
 }
 if(end-start == 1 && start<end)     //array has only two elements
 {
	if(p[start] > p[end])
	{
		temp = p[start];
		p[start] = p[end];
		p[end] = temp;
	}
	return;
 }
 else if(start == end)   // array has a single element
	return;
 msort(p,start,(start+end)/2);
 msort(p,(start+end)/2+1,end);
 j=start;
 if(mid+1 == end)             //mid is (start+end)/2 n array has three elements
 {
	if(p[start+1] < p[end])
	{
		q[j++] = p[start];
		q[j++] = p[start+1];
		q[j++] = p[end];
	}
	else
	{
		if(p[start] < p[end])
		{
			q[j++] = p[start];
			q[j++] = p[end];
			q[j++] = p[start+1];
		}
		else
		{
			q[j++] = p[end];
			q[j++] = p[start];
			q[j++] = p[start+1];
		}
	}
 }
 else
 {	
	 for(i=start,j=start ; i<mid ; i++)
	 {
		if(p[i] > p[i+mid])
		{
			temp = p[i];
			p[i] = p[i+mid];
			p[i+mid] = temp;
		}
		q[j++] = p[i];
		q[j++] = p[i+mid];
	 }
}
 dummy=p;    //this is not the dummy array as i talked of earlier its rather q
 p=q;
 free(dummy);
 printf("Now array is : ");
 for(i=start;i<=end;i++)
   printf("%d ",p[i]);
 puts("");
}

free(dummy)