Computer Science, GATE

Merge Sort

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

Myself Shubham an computer science engineer with lots of dream having an unseen attitude with lots of thoughts

Tagged , , ,

About Shubham Lashkan

Myself Shubham an computer science engineer with lots of dream having an unseen attitude with lots of thoughts
View all posts by Shubham Lashkan →

Leave a Reply

Your email address will not be published. Required fields are marked *