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

15 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
  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

Leave a Reply

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