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)

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:
1. MergeSort(low,mid)
2. MergeSort(mid+1,high)
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
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++;
}
}