**Merge Sort Algorithm:**

- Is based on the divide and conquer approach.
- Divides the list into two sublists of sizes as nearly equal as possible.
- Sorts the two sublists seperately by using merge sort.
- Merges the sorted sublists into one single list.

**Algorithm:**

MergeSort(low,high)

- if(low >= high)
- return

- Set mid = (low+high)/2
- Divide the list into two sublists of nearly equal lengths and sort each sublist by using merge sort. The steps to do this are as follows:
- MergeSort(low,mid)
- MergeSort(mid+1,high)

- Merge the two sorted sublists:
- set i = low
- set j = mid + 1
- set k = low
- Repeat until i > mid or j > high
**//This loop will terminates when you reach the end of one of the two //sublists.**- if(arr[i] <= arr[j])
- Store arr[i] at index k in array B
- Increment i by 1

- else
- store arr[j] at index k in array B
- Increment j by 1

- Increment k by 1

- if(arr[i] <= arr[j])
- Repeat until j > high
**//If there are still some elements in the second sublist append them to the new list**- Store arr[j] at index k in array B
- Increment j by 1
- Increment k by 1

- Repeat until i > mid
**//If there are still some elements in the first sublist append them to the new list**- Store arr[i] at index k in array B
- Increment i by 1
- Increment k by 1

- Copy all elements from the sorted array B in to the original array arr

### Implementing Merge Sort

#include<stdio.h>

#include<conio.h>

#define max 20

void mergesort(int a[],int low, int high);//Divides the array into halves

void merge(int a[],int low,int mid, int high);//Sort and merges subarray

int main()

{

int a[max],i=0,n=0;

printf(“Enter no. of elements\n”);

scanf(“%d”,&n);

printf(“Enter no.\n”);

for(i=0;i<n;i++)

scanf(“%d”,&a[i]);

printf(“Unsorted Array:\t”);

for(i=0;i<n;i++)

printf(“%d\t”,a[i]);

mergesort(a,0,n-1);

printf(“\nSorted Array:\t”);

for(i=0;i<n;i++)

printf(“%d\t”,a[i]);

return 0;

}

void mergesort(int a[],int low,int high)

{

if(low<high)

{

int mid = (low+high)/2;

mergesort(a,low,mid);

mergesort(a,mid+1,high);

merge(a,low,mid,high);

}

}

void merge(int a[],int low, int mid, int high)

{

int high1 = mid-low+1;

int high2 = high-mid;

int i=0,j=0,k=0;

int temp1[high1],temp2[high2]; //Temproary arrys

for(i=0;i<high1;i++) //copy array values in temp arrays

temp1[i] = a[low+i];

for(j=0;j<high2;j++)

temp2[j] = a[mid+1+j];

i=0;

j=0;

k=low;

while(i<high1 && j<high2) //compare elements of subarray

{

if(temp1[i]<temp2[j])

{

a[k] = temp1[i];

i++;

}

else

{

a[k] = temp2[j];

j++;

}

k++;

}

while(i<high1) //copy remaining elements as it is

{

a[k] = temp1[i];

i++;

k++;

}

while(j<high2)

{

a[k] = temp2[j];

j++;

k++;

}

}

**If you found any mistakes in above code then please let us know in the comment box below.**

For Gate CSE study material Click Here..!!