Merge sort program in c






Source code of simple merge sort implementation using array in ascending order in c programming language

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){
   
    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }
   
    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}


Sample output:

Enter the total number of elements: 5
Enter the elements which to be sort: 2 5 0 9 1
After merge sorting elements are: 0 1 2 5 9





5. Write a c program for heap sort.
7. Write a c program for shell sort.

13 comments:

  1. plz give me its algorithm..

    ReplyDelete
  2. i'm quiet confuse every time when more than two recursion function calling...plzzz give me some idea... & help me to solve such a situation ...

    ReplyDelete
  3. Thank you, sir. It works like a charm.

    ReplyDelete
  4. same here confused with more than one recursions :( can you give me some ideas

    ReplyDelete
  5. pls give its algo

    ReplyDelete
  6. the program contains 2 functions. The first 1 divides the list,in this case, the array into small chunks of items. each chunk having 1 or at most 2 items. here,we use recursion to divide the list into these chunks.

    the second function takes these chunks and set it in a temporary array temp[] according to its value. no recursion takes place here.
    left is 0, right=n-1 and mid=mid index.
    (u need to preserve the value of left and right.. so put them in variables say l,r)
    now a variable say t is initialized as 0,or left as left is 0.(it will provide index for temp[])
    compare the values in the merge[] for indexes l and mid. in case l is small, inc l by 1. if mid is small inc. mid by 1 and in both the steps put the small value in temp[].

    even i learnt it today only. and have some doubts in the final steps.
    i have no idea about why the penultimate if else statement is used. but i am sure about this much.

    #6/3/13.. i guess u have ur exam tomorrow.. even i have.. all the best..



    ReplyDelete
  7. Can u tell the formula for counting the number of times the basic operation is repeated??

    ReplyDelete
  8. penultimate if else is used for the case when either of the both half gets sorted while the remaining has not been sorted.This if else will sort the remaining part also.

    ReplyDelete
  9. when there is more than one recursive calls then the thing that should be noted is value will be received only in the calling function so u need to be aware that which function is calling and where's my value receiving.

    ReplyDelete
  10. why max 50 was used

    ReplyDelete
    Replies
    1. using max 50 is not a must. . . it s just 2 specify the array size. . .

      Delete