# Merge Sort C Program Implementation

This is the Implementation of Sorting Algorithm Merge Sort in C

merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

An example of merge sort. 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.

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

```
#include<stdio.h>
int arr[100],n,j=0;
main()
{
int i;
printf("Enter array Elementsn");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
mergesort(0,n-1);
printf("Sorted Listn");
for(j=0;j<n;j++)
{
printf("%dn",arr[j]);
}
}
mergesort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
conquer(low,mid,high);
}
}
conquer(int low,int mid,int high)
{
int i,j,res[100];
int index=low;
for(i=low,j=mid+1;(i<=mid)&&(j<=high);)
{
if(arr[i]<arr[j])
{
res[index]=arr[i];
index++;
i++;
}
else
{
res[index]=arr[j];
index++;
j++;
}
}
for(;i<=mid;i++,index++)
{
res[index]=arr[i];
}
for(;j<=high;j++,index++)
{
res[index]=arr[j];
}
for(i=low;i<index;i++)
{
arr[i]=res[i];
}
}
```

## Recent Comments