C Program Merge Sort

By | March 8, 2020

C Program Merge Sort

/*
C Program Merge Sort uses
merge sort method to sort 
N element array in ascending order
*/

#include<stdio.h>
 
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
 
int main()
{
	int a[100],n,i;
	printf("Enter no of elements in the Array [Maximum 100]: ");
	scanf("%d",&n);
	
	/*Input array elements (numbers to be sorted)*/
	printf("Enter %d array elements: \n",n);
	
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
		
	mergesort(a,0,n-1); /*call mergesort() for sorting the list*/
	
	printf("\nSorted array in ascending order using Merge Sort Algoithm is as follows:\n");
	/*output the sorted array*/
	for(i=0;i<n;i++)
		printf("%d, ",a[i]);
		
	return 0; 
}
 

void mergesort(int a[],int i,int j)
{
	int mid;
		
	if(i<j)
	{
		mid=(i+j)/2;
		mergesort(a,i,mid);		/*call Merge sort for left sub list*/
		mergesort(a,mid+1,j);	/*call merge sort for right sub list*/
		merge(a,i,mid,mid+1,j);	/*call merge for merging of two sorted sub-arrays*/
	}
}
 
void merge(int a[],int i1,int j1,int i2,int j2)
{
	int temp[100];	/*temporary array used for merging*/
	int i,j,k;
	i=i1;	/*start of the first list*/
	j=i2;	/*start of the second list*/
	k=0;
	
	while(i<=j1 && j<=j2)	/*while elements in both lists*/
	{
		if(a[i]<a[j])
			temp[k++]=a[i++];
		else
			temp[k++]=a[j++];
	}
	
	while(i<=j1)	/*copying remaining elements of the first list*/
		temp[k++]=a[i++];
		
	while(j<=j2)	/*copying remaining elements of the second list*/
		temp[k++]=a[j++];
		
	/*Transfer elements from temporary array temp[] back to original array a[]*/
	for(i=i1,j=0;i<=j2;i++,j++)
		a[i]=temp[j];
}

Output

Enter no of elements in the Array [Maximum 100]: 10
Enter 10 array elements:
9
8
5
3
7
8
1
2
10
11

Sorted array in ascending order using Merge Sort Algoithm is as follows:
1, 2, 3, 5, 7, 8, 8, 9, 10, 11,
——————————–
Process exited after 50.36 seconds with return value 0
Press any key to continue . . .

Leave a Reply

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