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.

24 comments:

Anonymous said...

plz give me its algorithm..

Anonymous said...

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

Anonymous said...

Thank you, sir. It works like a charm.

Anonymous said...

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

Anonymous said...

pls give its algo

Anonymous said...

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



Anonymous said...

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

Anonymous said...

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.

Anonymous said...

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.

Anonymous said...

why max 50 was used

Anonymous said...

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

Unknown said...

thank u.

Information said...

THANK YOU SO MUCH

Unknown said...

Just start drawing recursion tree, Also keep in mind every block or function maintains separate stack of local variables :D

Anonymous said...

The condition on "if(low<high)" in partition() function should be "if(high - low < 2)". I tried your code, when I used 1 million numbers, everything was okay. But, when I used more and more numbers (about 10 millions numbers), there was a segmentation fault. I have no idea why it happened. If I'm using "if(high - low < 2)", it just works fine.

Thanks for your code, though.

Anonymous said...

ups my bad, using "(high - low < 2)" makes getting worse, it screws up the result.
I think the segmentation fault problem is occured because of huge number of data is used when temp[max] is initialized.

Anonymous said...

problem solved. I should initialize temp to -> temp[max+1]

Anonymous said...

*) int temp[high+1], or
int *temp = malloc((high+1) * sizeof(int));

Unknown said...

#include
void main()
{
int A[10],B[10],C[20];
int i, j,k;
int n1,n2,n3;

printf(" Enter the number of elements in A[] \n");
scanf("%d", &n1);
printf(" Enter the Array elements of A[] in sorted form \n");
for (i = 0; i < n1; i++)
scanf("%d", &A[i]);
printf(" A[] Entered is \n");
for (i = 0; i < n1; i++)
printf(" %d", A[i]);
printf("\n Enter the number of elements of B[] \n");
scanf("%d", &n2);
printf(" Enter the Array elements of B[] in sorted form\n");
for (i = 0; i < n2; i++)
scanf("%d", &B[i]);
printf(" B[] Entered is \n");
for (i = 0; i < n2; i++)
printf(" %d", B[i]);
i=0;j=0;
k=0;
while (i<n1 && j<n2)
{
if (A[i]<=B[j])
{
C[k]=A[i];
i++;
}
else
{
C[k]=B[j];
j++;
}
k++;
}
while (i<n1)
{

C[k]=A[i];
i++;
k++;
}
while (j<n2)
{

C[k]=B[j];
j++;
k++;
}

n3=n1+n2;
printf("\n New Array is...\n");
for (i = 0; i < n3; i++)
printf(" %d",C[i]);
}

Unknown said...

#include
void main()
{
int A[10],B[10],C[20];
int i, j,k;
int n1,n2,n3;

printf(" Enter the number of elements in A[] \n");
scanf("%d", &n1);
printf(" Enter the Array elements of A[] in sorted form \n");
for (i = 0; i < n1; i++)
scanf("%d", &A[i]);
printf(" A[] Entered is \n");
for (i = 0; i < n1; i++)
printf(" %d", A[i]);
printf("\n Enter the number of elements of B[] \n");
scanf("%d", &n2);
printf(" Enter the Array elements of B[] in sorted form\n");
for (i = 0; i < n2; i++)
scanf("%d", &B[i]);
printf(" B[] Entered is \n");
for (i = 0; i < n2; i++)
printf(" %d", B[i]);
i=0;j=0;
k=0;
while (i<n1 && j<n2)
{
if (A[i]<=B[j])
{
C[k]=A[i];
i++;
}
else
{
C[k]=B[j];
j++;
}
k++;
}
while (i<n1)
{

C[k]=A[i];
i++;
k++;
}
while (j<n2)
{

C[k]=B[j];
j++;
k++;
}

n3=n1+n2;
printf("\n New Array is...\n");
for (i = 0; i < n3; i++)
printf(" %d",C[i]);
}

Unknown said...

Please Teach me some Programing....We are learning algorithm and i am not able to understand anything in class...Please if you could help me i will be gratefull to sir

Unknown said...

Teach me some logics in programing....i couldn't understand anything in class...please help me

Unknown said...

#include
void mergeSort(int*, int, int);
using namespace std;
void main() {
int x[] = { 2,12,3,4,7,5,8,12,13,1,9,11,10,1,6,23,45,443,345,1,2,7,6,23,45 };
mergeSort(x, 0, 24);
for (int i = 0; i < 25; i++)
cout << x[i] << ",";
cout << endl;
system("pause");
}

void mergeSort(int *x, int start1, int end2) {
if (start1 >= end2)
return;
int i, j, k, end1 = (start1 + end2) / 2, start2 = end1 + 1, A[20], B[20], n1 = start2 - start1, n2 = end2 - end1;
mergeSort(x, start1, end1);
mergeSort(x, start2, end2);
for (i = 0; i < n1; i++)
A[i] = x[start1 + i];
for (i = 0; i < n2; i++)
B[i] = x[start2 + i];
i = j = k = 0;
while (i < n1 && j < n2)
if (A[i] < B[j])
x[start1 + k++] = A[i++];
else
x[start1 + k++] = B[j++];
if (i == n1)
while (j < n2)
x[start1 + k++] = B[j++];
else if (j == n2)
while (i < n1)
x[start1 + k++] = A[i++];
}

Unknown said...

give me the pseudo code for merge sort