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 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.
 
Merge Sort Animation
Merge sort algorithm diagram
 

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];
}
 

C Program for Implementation of Merge Sort
 
If you have any doubts regarding above program for merge sort in C then comment below.

56 thoughts on “Program for Merge Sort in C”

  1. 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. 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.

      1. 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.

    1. temp[k] is the array where all sorted elements are stored. using the for loop we display the temp array ..hope you got it

  2. 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.

  3. //////////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. 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.

    2. 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.

    3. 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

      1. 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.

  4. 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 ?

    1. gourav Singh thakur

      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

  5. 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

  6. 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.

    1. 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]);

  7. excellent work but if u will elaborate the concept of how recursion works here , it would be very helpful

  8. 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

  9. Sir my code doesn’t work after entering the array element ……..means it doesn’t give the sorted list …..

  10. 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];
    }

  11. 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

    1. #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];
      }

Leave a Comment

Your email address will not be published. Required fields are marked *