Program of a merge sort is below. Divide the first list into the smallest unit, then compare each element with the adjacent list to sort and merge two adjacent lists.Finally all the elements are getting sorted and merged.
C Program – Merge Sort Program implementation
#include<stdio.h>
void merge_sort(int arr[],int i,int j);
void merge(int arr[],int i1,int j1,int i2,int j2);
int main()
{
int arr[40],num,i;
printf("how many number of elements do you want to enter?:");
scanf("%d",&num);
printf("Enter the array of elements:");
for(i=0;i<num;i++)
scanf("%d",&arr[i]);
merge_sort(arr,0,num-1);
printf("\nSorted elements of array are:");
for(i=0;i<num;i++)
printf("%d ",arr[i]);
return 0;
}
void merge_sort(int arr[],int i,int j)
{
int mid;
if(i<j)
{
mid=(i+j)/2;
merge_sort(arr,i,mid);
merge_sort(arr,mid+1,j);
merge(arr,i,mid,mid+1,j); //merging two sorted sub-arrays
}
}
void merge(int arr[],int k,int l,int m,int n)
{
int temp[50]; //array used for merging
int i,j,p;
i=k; //beginning of the first list
j=m; //beginning of the second list
p=0;
while(i<=l && j<=n) //while elements in both lists
{
if(arr[i]<arr[j])
temp[p++]=arr[i++];
else
temp[p++]=arr[j++];
}
while(i<=k) //copy remaining elements of the first list
temp[p++]=arr[i++];
while(j<=n) //copy remaining elements of the second list
temp[p++]=arr[j++];
//Transfer elements from temp[] back to a[]
for(i=k,j=0;i<=n;i++,j++)
arr[i]=temp[j];
}
Output:-
