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

10 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

Leave a Reply

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