In this tutorial, you will get program for merge sort in C.
Merge sort runs in O (n log n) running time. It is a very efficient sorting data structure algorithm with near optimal number of comparisons. 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
#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.
Hey sorry, but still i didn’t get about the right recursive function. There will be three iteration of left recursion and after that when value of p,q,r becomes 0,1,0 then it will perform the next statement which is right recursion.
How you have taken array for temp to array of a that for loop i didnt understand
using keyboard
very good question
temp[k] is the array where all sorted elements are stored. using the for loop we display the temp array ..hope you got it
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
First u need do complete the declaration of header files.. like #include .
And after that u must need too declare your function definitions after those header files.
starting two lines are incorrect and return zero shouldn’t be required here.if u really want to see that the program is corect or not then execute in turbo C++….dont do show off
First two lines are incomplete.
i am vreri vreri intreshtead programing
why we copy remaining elements of the first list and second list?
For eg out of 2 arrays , left side array got sorted which means all remaining elements of right array are greater than greatest element of left array so print remaining elements.
Den can u tell me you v have to use K in merging?
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 ?
bro for every fuctn call a activation record in the form of stack is created in the memory and at same the program counter value for next statement is saved …when this I<j condition becomes false pop operation will be performed along with the completion of next statement that time rightside recusion will carry out in same manner
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.
Plz explain it by using its algorithm
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.
Please provide logic calculations for this program
nice
why not dynamically allocate?
Thank you it is vrey usefull.
This is great! Thank you so much 🙂
I made some minor modifications when declaring the arrays though:
1st modification:
originial:
| 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]);
my version:
| int n;
| printf("Enter no of elements:");
|
| int a[n], i;
| scanf("%d",&n);
| printf("Enter array elements:");
| for(i=0;i<n;i++)
| scanf("%d",&a[i]);
2nd modification:
originial:
void merge(int a[],int i1,int j1,int i2,int j2)
{
int temp[50]; //array used for merging
my version:
void merge(int a[],int i1,int j1,int i2,int j2)
{
int temp[j2-i1+1]; //array used for merging
As I understand, this would declare just enough elements for each array.
1st modification I put some lines in slightly akward order! Should have looked like this
my version:
| int n;
| printf(“Enter no of elements:”);
| scanf(“%d”,&n);
|
| int a[n], i;
| printf(“Enter array elements:”);
| for(i=0;i<n;i++)
| scanf("%d",&a[i]);
excellent work but if u will elaborate the concept of how recursion works here , it would be very helpful
can u explain how recursion is working internally in this program,recursion concepts are not clear of mine,it would be very nice of u
I was wondering if you could write the code with c++……..
thanks a lot…
Can anyone explain or expand this loop
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
Sir my code doesn’t work after entering the array element ……..means it doesn’t give the sorted list …..
pls can i get the code for merge sort in c++?
instead of i and j in the last for loop use the variable k alone.
for(k=low;k<=high;k++)
{
a[k]=temp[k];
}
Is it Merge Sort time complexit?
Void main( ) missing
very helpfull
Can u please explain the program clearly
With the use of variables used and so on!
Please upload algorithm as well…
mast program
i love u
Great
Hello
cool
Implement a Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements. The elements can be read from a file or can be generated using the random number generator.
i want the solution of this question
Plz mail me the solution
#include
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);
mergesort(a,mid+1,j);
merge(a,i,mid,mid+1,j);
}
}
void merge(int a[],int i1,int j1,int i2,int j2)
{
int temp[50];
int i,j,k;
i=i1;
j=i2;
k=0;
while(i<=j1 && j<=j2)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=j1)
temp[k++]=a[i++];
while(j<=j2)
temp[k++]=a[j++];
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}