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.

 

Merge Sort Animation

 

Merge sort algorithm diagram

Program for Merge Sort in C


 

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

Category: DSA

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

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

      Reply
  2. eshu

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

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

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

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

      Reply
    2. Kartik joshi

      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.

      Reply
    3. saurav shirbhate

      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

      Reply
  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 ?

    Reply
  6. muhammad irfan

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

    Reply
  7. Suraj R Bhuyar

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

    Reply
    1. Admin Post author

      It is inbuilt compiler feature. I am using codeblocks.

      Reply
  8. Younes

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

    Reply
  9. 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

    Reply
  10. troy

    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.

    Reply
    1. troy

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

      Reply
  11. sahil raina

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

    Reply
  12. sahil raina

    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

    Reply
  13. Hassan

    I was wondering if you could write the code with c++……..
    thanks a lot…

    Reply

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.