Merge sort

Merge sort is comparison-based sorting algorithm. Merge sort is a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

Algorithm

MERGE (A,p,q,r)
1.	n1 = q + p + 1
2. n2 = r + q
3.	let L[1. . n1 + 1] and R[1 . . n2 + 1] be new arrays
4. for i = 1 to n1
5. 	L[i] = A[p + i + 1]
6. for j = 1 to n2
7. 	R[j ] = A[q + j]
8. L[n1 + 1] = 9999
9. R[n2 + 1] = 9999
10. i = 1
11. j = 1
12. for k = p to r
13. 	if L[i] <= R[j ]
14. 		A[k] = L[i]
15.		 i = i + 1
16. 	else A[k] = R[j]
17. 		j = j + 1

Merge sort Implementation

#include<stdio.h>
#include<conio.h>
int arr[20];       
void main()
{
	int n,i;
	clrscr();
	printf("\n\t\t\t------Merge Sorting------\n\n");
	printf("Enter the size of array\n");
	scanf("%d",&n);
	printf("Enter the elements:\n");
	for(i=0; i < n; i++)
	{
		scanf("%d",&arr[i]);
	}
	merge_sort(arr,0,n-1);
	printf("\n\n\t\t\t-----Merge Sorted Elements-----\n\n");
	printf("Sorted array:\t");
	for(i=0; i < n; i++)
	{
		printf("\t%d",arr[i]);
	}
	getch();
}

int merge_sort(int arr[],int low,int high)
{
	int mid;
	if(low < high)
	{
		mid=(low+high)/2;
		merge_sort(arr,low,mid);
		merge_sort(arr,mid+1,high);
		merge(arr,low,mid,high);
	}
}
int merge(int arr[],int l,int m,int h)
{
	int arr1[10],arr2[10];
	int n1,n2,i,j,k;
	n1=m-l+1;
	n2=h-m;
	for(i=0; i <  n1; i++)
	{
		arr1[i]=arr[l+i];
	}
	for(j=0; j < n2; j++)
	{
		arr2[j]=arr[m+j+1];
	}
	arr1[i]=9999;
	arr2[j]=9999;
	i=0;
	j=0;
	for(k=l; k <=h; k++)
	{
		if(arr1[i]<=arr2[j])
			arr[k]=arr1[i++];
		else
			arr[k]=arr2[j++];
	}
}

OUTPUT