Group Discounts available for 3+ students and Corporate Clients

Explain about Merge Sort in DataStructures

Merge Sort

  • Merging a two lists of one element each is the same as sorting them.
  • Merge sort divides up an unsorted list until the above condition is met and then sorts the divided parts back together in pairs.
  • Specifically this can be done by recursively dividing the unsorted list in half, merge sorting .The right side then the left side and then merging the right and left back

 

Merge sort algorithm:

Given a list L with a length K:

If k==1  7 the list is sorted

else

  • merger sort the left side( 0thru k/2)
  • merge sort the right side (k/2+1 thru K)
  • merge the right with the left side.

91

 

 

 

program: Implementation of merge sort

 

# include <stdio.h>

#include <conio.h>

void merge (int numbers [], int temp[], int left,  int mid ,  int right);

void merge sort (int numbers[], int temp[], int array-size);

void m-sort( int numbers[],int temp[],int left, int right);

void merge-sort ( int numbers [],int temp, int array-size);

{

m-sort(numbers,temp,0,array-size-1);

}

void m-sort(int numbers[],int temp[],int left, int right)

{

int mid;

if(right>left)

{

mid = (right +left)/2;

m-sort (numbers,  temp, left,mid);

m-sort(numbers temp,mid+1,right);

merge(numbers,temp,left,mid+1,right);

}

/*merge*/

void merge(int numbers[],int temp[],int left, int mid, int right)

{

int i,left-end,num-elements,Emp-pos;

left-end =mid-1;

emp-pos-left;

num-elements =right-left+1;

while ((left<=left-end)&& (mid<=right))

{

if(numbers[left]<=numbers[mid])

{

temp[temp-pos]=numbers[left];

tmp-pos = tmp-pos+1;

left=left+1;

else

{temp[tmp-pos]= numbers [mid];

tmp-pos=tmp-pos+1;

mid=mid+1;

}

}

while( left <= left-end)

{

temp (tmp-pos]= numbers[left];

left=left+1;

tmp=pos=tmp=pos+1;

}

while(mid <=right)

{

temp[tmp-pos]= numbers[mid];

mid=mid+1;

tmp-pos=tmp-pos+1;

}

for(i=0;i<=num-elements;i++)

{

numbers [right ]= temp[right];

right =right-1;

}

}

void main()

{

int a[20],b[20],n,i;

printf(“Enter the value of  n:\n”);

scanf(“%d”,&n);

printf(“Enter n elements :\n”);

for (i=0;i<=n;i++)

{

scanf(“%d”,&a[i]);

}

merger sort(a,b,n);

printf (“Sorted elements are :\n”);

for (i=0;i<n;i++)

{

printf(“%d”,a[i]);

}

}

 

 

 

 

OUTPUT:

Enter the value of n:8

Enter n elements:

18 26 32 6 43 15 9 1

sorted elements are:

1  6  9 15 18  26 32 43

 

 

 

 

 

 

 

 

 

 

 

 

Example: 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

“At TekSlate, we are trying to create high quality tutorials and articles, if you think any information is incorrect or want to add anything to the article, please feel free to get in touch with us at info@tekslate.com, we will update the article in 24 hours.”

0 Responses on Explain about Merge Sort in DataStructures"

    Leave a Message

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

    Support


    Please leave a message and we'll get back to you soon.
    Three + 6