## Merge Sort

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)

1. if(low >= high)
• return
2. Set mid = (low+high)/2
3. 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:
1. MergeSort(low,mid)
2. MergeSort(mid+1,high)
4. Merge the two sorted sublists:
1. set i = low
2. set j = mid + 1
3. set k = low
4. Repeat until i > mid or j > high //This loop will terminates when you reach the end of one of the two //sublists.
1. if(arr[i] <= arr[j])
1. Store arr[i] at index k in array B
2. Increment i by 1
2. else
1. store arr[j] at index k in array B
2. Increment j by 1
3. Increment k by 1
5. Repeat until j > high //If there are still some elements in the second sublist append them to the new list
1. Store arr[j] at index k in array B
2. Increment j by 1
3. Increment k by 1
6. Repeat until i > mid  //If there are still some elements in the first sublist append them to the new list
1. Store arr[i] at index k in array B
2. Increment i by 1
3. Increment k by 1
5. 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.