# Merge sort

Last Updated on

## Working of Merge sort

Merge sort is one of the sorting algorithms, this follows Divide and Conquer rule to sort the given elements. In the merge sort, the unsorted array of size is divided into n subparts, these subparts are sorted itself because there is no other element, so these subparts are compared to the other parts and arranged in the sorted format. After the sorting of the subparts or individual elements then they are merged together to make a new sub-array(subpart)

In Merge sort, the complex thing is divided into some parts and these are merged together to attain the solution. here the unsorted array is divided into two parts, if the no of elements is even then the first sub-parts will be equal ex: (8/2)=4, if the total no of elements is odd then first subpart of the array should greater than the second part

**size of the unsorted array == number of sub parts**

- In the above example, the no of elements Is 6, so this is divided into two parts with each 3 elements
- the subparts are divided into each individual
- these individuals are compared with each other, that which is greater among them
- last the individuals merge into sub-parts again with the sorted elements
- sub-parts are merged into a single sorted array

## The Time complexity of merge sort

- Worst Case Time Complexity [ Big-O ]:
**O(n*Log n)** - Best Case Time Complexity [Big-omega]:
**O(n*Log n)** - Space Complexity:
**O(n*Log n)**

## Program for Merge sort

```
#include<stdio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
int main()
{
int a[30],n,i;
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nSorted array is :");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
void mergesort(int a[],int i,int j)
{
int mid;
if(i<j)
{
mid=(i+j)/2;
mergesort(a,i,mid); //left recursion
mergesort(a,mid+1,j); //right recursion
merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays
}
}
void merge(int a[],int i1,int j1,int i2,int j2)
{
int temp[50]; //array used for merging
int i,j,k;
i=i1; //beginning of the first list
j=i2; //beginning of the second list
k=0;
while(i<=j1 && j<=j2) //while elements in both lists
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=j1) //copy remaining elements of the first list
temp[k++]=a[i++];
while(j<=j2) //copy remaining elements of the second list
temp[k++]=a[j++];
//Transfer elements from temp[] back to a[]
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}
```