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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<stdio.h> void mergesort(int a[],int i,int j); void merge(int a[],int i1,int j1,int i2,int j2); int main() { int a[30],n,i; printf("Enter no of elements:"); scanf("%d",&n); printf("Enter array elements:"); for(i=0;i<n;i++) scanf("%d",&a[i]); mergesort(a,0,n-1); printf("\nSorted array is :"); for(i=0;i<n;i++) printf("%d ",a[i]); return 0; } void mergesort(int a[],int i,int j) { int mid; if(i<j) { mid=(i+j)/2; mergesort(a,i,mid); //left recursion mergesort(a,mid+1,j); //right recursion merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays } } void merge(int a[],int i1,int j1,int i2,int j2) { int temp[50]; //array used for merging int i,j,k; i=i1; //beginning of the first list j=i2; //beginning of the second list k=0; while(i<=j1 && j<=j2) //while elements in both lists { if(a[i]<a[j]) temp[k++]=a[i++]; else temp[k++]=a[j++]; } while(i<=j1) //copy remaining elements of the first list temp[k++]=a[i++]; while(j<=j2) //copy remaining elements of the second list temp[k++]=a[j++]; //Transfer elements from temp[] back to a[] for(i=i1,j=0;i<=j2;i++,j++) a[i]=temp[j]; } |

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

cool

what is the compiler used here?

I have used gcc compiler and codeblocks ide.

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.

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.

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

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.

//////////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;

}

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.

U just put in header

#include

#include

i am vreri vreri intreshtead programing

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

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:

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

It is inbuilt compiler feature. I am using codeblocks.

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

THANKS BROTHER

U MADE IT LOOK SIMPLE…

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

please calculate the time complexity

It simplifies a begginers approach. Great work.