Merge Sort
Computer Science, GATE

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.

For Gate CSE study material Click Here..!!

Learn Quick Sort Algorithm From Here