# Program for Merge Sort in C

In this tutorial you will get program for merge sort in C.

Merge sort runs in O (n log n) running time. It is very efficient sorting algorithm with near optimal number of comparison. Recursive algorithm used for merge sort comes under the category of divide and conquer technique. An array of n elements is split around its center producing two smaller arrays. After these two arrays are sorted independently, they can be merged to produce the final sorted array. The process of splitting and merging can be carried recursively till there is only one element in the array. An array with 1 element is always sorted.

An example of merge sort in C is given below. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

## Program for Merge Sort in C

If you have any doubts regarding above program for merge sort in C then comment below.
Category: DSA

## 21 thoughts on “Program for Merge Sort in C”

1. Raj mishra

when left recursion is performed then recursively function is called and when i<j condition false then program execution stopped then when right recursion is performed.

1. Rayudu

I hope you may know C follows top to bottom approach when the statement finished execution immediately the compiler executes the next statement.

So after completing the left recursion it comes back and starts the next execution of next statement.

2. eshu

How you have taken array for temp to array of a that for loop i didnt understand

3. shivom

why are you using temp[50] when your original array is of 30 elements only. i am having this problem in my code that it does segmentation fault if i define temp array of same size as of my original array. but my program runs fine when i define large temp array.

4. mudit agrawal

//////////what’s wrong with this code can anybody please tell me…ivalid indirection is what erroe it i showing…/////
#include
#include
void main()
{
int a[20],i,n;
printf(“enter the length of the array\n”);
scanf(“%d”,&n);
printf(“enter the elements in the array\n”);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
merge_sort(a,1,n);
printf("the sorted array is\n");
for(i=1;i<=n;i++)
printf("%d",a[i]);
}
int 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);
}
return 0;
}
merge(int a, int p, int q,int r)
{
int k,i,j,c,b,L[20],R[20];
c=q-p+1;
b=r-q;
for(i=1;i<=c;i++)
{
L[i]=a[p+i-1];
}
for(j=1;j<=b;j++)
{
R[j]=a[q+j];
}
i=1;
j=1;
for(k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
j++;
}
}
return 0;
}

1. Troy

Your first two lines are incomplete.

#include
#include

Also, there won’t be return 0 at the end if you are defining main function as void.

1. neel

why we copy remaining elements of the first list and second list?

5. Varun

I have the same question in my mind as questioned by raj mishra .
when left recursion is performed then recursively function is called and when i<j condition false then program execution stopped then when right recursion is performed ?

hy how r sir how to combine quick sort ,heapsort, mergesort in switch statement plz send me the source
code for it:

7. Suraj R Bhuyar

hello sir… how u calculated the time taken for execution in the above program?

It is inbuilt compiler feature. I am using codeblocks.

8. Younes

could you please do a c++ code for the same sorting algorithm.

9. YUVRAJ SHARMA

THANKS BROTHER

10. ama

Yes Yes Yes.I do have a doubt.
mergesort(a,i,mid); //left recursion
mergesort(a,mid+1,j); //right recursion
As per my understanding left recursion will execute until the condition is false and then the control moves over to the right recursion.
My question is at mergesort(a,mid+1,j),the new values of mid ,low and high will be from main function? OR from the mergesort(a,i,mid) ?
And the same question applies here too :
mergesort(a,mid+1,j); //right recursion
merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays

11. jamisetti nikhil