ALGORITHM:
Conceptually, a merge sort works as follows
- 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 sublists until there is only 1 sublist remaining. (This will be the sorted list.)
function merge_sort(list m)
// if list size is 1, consider it sorted and return it
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after or equal middle
add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)
ANIMATION:
CODE:
/* WWW.CODE-AHOLIC.BLOGSPOT.IN- MERGE SORT */
#include<stdio.h>
#include<conio.h>
#define MAX 50
void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);
void 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]);
getch();
}
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];
}
}