Merge Sort in Data structure is another simple sorting techniques. It is a simple technique to sort the element.

Page Contents

## Merge sort

Merge sort is a divide and conquer algorithm. Merge sort keeps on dividing the list into equal halves until it can no more be divided and perform sorting.
Merge sort is also used for sorting two individual unsorted lists to the sorted list. It merges the list.

### Merge sort technique

In this technique we have an N number of an unsorted list in this; we divide each element into a separate partition.
First, we divide the whole list into two arrays then that two arrays are divided separately and sort each element after that we merge the partitioned set to one single array. Finally, We will get our sorted array by merge sort technique.

### Merge Sort Example:

The following diagram is merge sort in Data structure example which shows the complete process to sort an array using merge sort in data structure technique. Let’s see in detail using example

How merge sort works?
The array to sort is 30, 27, 43, 3, 9, 82, 10
The given array is recursively divided into two halves till the size become 1.

Pass 1: –
Mid = (Start + end) /2
Start = 0 and end = 6
So, we get mid = (0+6)/2 = 3
At pass 1 we get two halves
First half = 38, 27, 43, 3
Second half = 9, 82, 10

Pass 2: –
At pass 2 we get new two halves for both first and second half
First half = 38, 27 second half = 43, 3
Third half = 9, 82 Fourth half= 10

Pass 3: –
Continue with dividing halves
First half = 38 second half = 27 Third half = 43 forth half = 3
Fifth half = 9 Sixth half = 82 seven half= 10

After size became 1 start merging the array back till whole array is merged.

Pass 4:-
Start merging the halves
First half = 27, 38 second half = 3, 43
Third half = 9, 82 Fourth half= 10

Pass 5:-
Merge the halves
First half = 3, 27, 38, 43
Second half = 9, 10, 82

Pass 6: –
Merge the halves
Final array = 3, 9, 10, 27, 38, 43, 82

The sorted list is – 3 9 10 27 38 43 82
In this way, we will get the sorted list.
Passes required for sorting this array N-1 = 7-1 = 6. As we have 5 number passes are 6.

The passes or steps required for implementing merge sort is N -1.

### Merge sort algorithm

Mergesort(arr[],I,j)
if i < j

1. Find the middle point and divide the array into two halves. mid= (i+j)/2
2. Call merge sort for the first half. mergesort(a,i,mid);
3. Call Merge sort for the second half. mergesort(a,mid+1,j
4. Merge two halves sorted in step 2 and 3. merge(a,i,mid,mid+1,j);

### Flowchart for Merge sort

The following diagram shows the complete flow of the merge sort algorithm.

### Merge sort program in c

```#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];
}```

### The complexity of Merge sort

The time complexity for Merge sort
The worst-case and average-case time complexity of Merge sort is O(NlogN).
The Best case complexity of Merge sort is O(NlogN).
Space complexity for Merge sort: O(N)