MERGE SORT

/*
 * Merge Sort -
 * This is recursive function
 * O(n log(n))
  */


void merge_sort(int *list,int start,int end)
{
   /* recursing should be stoppped if start > end */
    if(start<end)
    {
        /* swap for merging two elements*/
        if(end-start == 1)
        {
            if(list[start]>list[end])
            {
                list[end]   = list[end] ^ list[start];
                list[start]   = list[end] ^ list[start];
                list[end] = list[end] ^ list[start];
            }
        }
        else
        {

            merge_sort(list,start, (start+end)/2);
            merge_sort(list,(start+end)/2+1,end);
            merge(list,start,(start+end)/2,end);
        }
    }
}

/*
 * Function to merge two arrays
 * To avoid memory wastage malloc used. Otherwise array of max size can be used
 */
void merge(int *list,int start,int middle,int end)
{
    int i,j,k,l;
    int *temp; /* if not dynamic max size should be used*/

    temp = (int *)malloc(sizeof(int)*(end-start+1));
    i=start;
    j=middle+1;
    k=0;
    while(1)
    {
       /* store the small element into temp array*/
        if(list[i]<list[j])
        {
            temp[k++]=list[i++];
        }
         else
        {
            temp[k++] = list[j++];
        }
      /* Check if any of the arrays are finished. If so append the other array*/
        if(i>middle)
        {
            for(;j<=end;j++)
                temp[k++]=list[j];
            break;
        }
        else if(j>end)
        {
            for(;i<=middle;i++)
                temp[k++]=list[i];
            break;
        }
    }
   /*  Fill the original array with merge sorted*/
    k=0;
    for(i=start;i<=end;i++)
    {
        list[i]=temp[k++];
    }

}