Techknow Study

merge sort

11:56:00 PM vikas 2 Comments Category :


 







merge sort 

Merge sort is based on divide and conquer method, which repeatedly cut then problem into

"equal halves" and sort them by following divide and conquer method recursively.

#include<conio.h>

#include<stdio.h>
#define size 5
int a[size],b[size];
void merge_sort(int first,int last);
void merge(int lf,int ll,int rf,int rl);
void main()
{
int i;
clrscr();
printf("enter the element");
for(i=0;i<=size;i++)
{
scanf("%d",&a[i]);
}
merge_sort(0,size);
 getch();
}
void merge_sort(int first,int last);
{
int middle;
if (first<last)
{
middle=(first+last)/2;
merge_sort(first,last);
merge_sort(middle+1,last);
merge(first,middle,middle+1,last);
void merge(int lf,int ll,int rf,int rl)
{
int prev_fst,temp;
prev_fst=lf;
temp=0;
while(lf<=ll && rf<=rl)
{
if(a[lf]<a[rf])
{
b[temp]=a[lf];
lf++;
temp++;
else
{
 b[temp]=a[rf];
rf++;
temp++;
}
}
while(lf<=ll)
{
b[temp]=a[lf];
lf++;
temp++;
 }
while(rf<=rl)
{
b[temp]=a[rf];
rf++;
temp++;
}
while(prev_fst<rl)
{
a[prev_fst]=b[temp]
prev_fst++;
temp++;
}
}
}
...

RELATED POSTS

2 comments