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

## 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

- Find the middle point and divide the array into two halves. mid= (i+j)/2
- Call merge sort for the first half. mergesort(a,i,mid);
- Call Merge sort for the second half. mergesort(a,mid+1,j
- 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]; }

#### Output:

### 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)

### Advantages of merge sort

- Merge sort is very simple and easy sorting technique.
- Merge sort works very good for large data.

### The disadvantage of merge sort

- This technique requires extra space for implementation.
- Merge sort is less efficient.