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..!!