# Merge Sort

Merge sort is the divide and conquer method to arrange elements in the order.The steps followed in merge sort are :

• Divide the sequence of n elements into two sub-sequences of n/2 elements each.
• Sort the sub-sequences using merge sort.If the size of sequence is 1,nothing more can be done.
• Merge the sub-sequences to form a sorted sequence of elements.

The complexity of merge sort is O(n log n).It runs faster than insertion and bubble sort but requires large amount of memory.

Program

```#include<stdio.h>
void merge(int [],int ,int ,int );
void partition(int [],int ,int );
int main()
{
int a[20];
int i,size;
printf("Unsorted List:\t");
//printf("Enter total no. of elements : ");
scanf("%d",&size);
for(i=0; i<size; i++)
{
scanf("%d",&a[i]);
printf("%d\t",a[i]);
}
printf("\n");
partition(a,0,size-1);
printf("Sorted List  :\t");
for(i=0; i<size; i++)
printf("%d \t",a[i]);
return 0;
}
void partition(int a[],int min,int max)
{
int mid;
if(min<max)
{
mid=(min+max)/2;
partition(a,min,mid);
partition(a,mid+1,max);
merge(a,min,mid,max);
}
}
void merge(int a[],int min,int mid,int max)
{
int temp[20];
int i,j,k,m;
j=min;
m=mid+1;
for(i=min; j<=mid && m<=max ; i++)
{
if(a[j]<=a[m])
{
temp[i]=a[j];
j++;
}
else
{
temp[i]=a[m];
m++;
}
}
if(j>mid)
{
for(k=m; k<=max; k++)
{
temp[i]=a[k];
i++;
}
}
else
{
for(k=j; k<=mid; k++)
{
temp[i]=a[k];
i++;
}
}
for(k=min; k<=max; k++)
a[k]=temp[k];
}
```

Example

Consider a sequence 7,44,2,10,1,35,74,88,5,3,15.We need to sort this  using merge sort.The list contains 11 elements(Fig 1).Divide the list such that first sub-list has 6 elements and second sub-list has 5 elements(vice-versa is also possible).Keep on dividing till we get single elements in the last.After dividing merge all the elements step by step as shown in Fig 2.

Rate this post