Your Ad Here

Thursday, July 5, 2007

Merge Sort

Merging is the process of combining two or more sorted arrays into a third sorted array. We can use this technique to sort an array of n elements as follows.
Divide the array into ‘n’ sub arrays of size 1 and merge adjacent pairs of sub arrays. Then we can have approximately n/2 sorted sub arrays of size 2. Repeat this process until there is 1 array containing n elements.
Algorithm
1. Establish a sub array ‘a’ with n elements
2. Let size < - 1 3. Repeat steps 4 through 6 until size >= n
4. Subdivide the sub array into sub arrays of size ‘size’
5. Merge adjacent pairs of sub arrays
6. Double the size

/*** C Program For Implementation Of Merge Sort ***/

#define MAX 20

void mergesort(int *,int);
void main()
{
int x[MAX],n,j,i;
char ans;
clrscr();
{
printf("\nEnter The Length Of The Array\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("Enter Element %d\t: ",i+1);
scanf("%d",&x[i]);
}
mergesort(x,n);
printf("\n\t│ Sorted Array :\t\t\t│\n\t│");
for(i=0;i< n;i++)
printf("%d\t",x[i]);
}
printf("│");
getch();
}

void mergesort(int x[],int n)
{
int sub[MAX];
int i,j,k,list1,list2,u1,u2,size=1;
while(size< n)
{
list1=0;
k=0;

while((list1+size)< n)
{
list2=list1+size;
u1=list2-1;
u2=((list2+size-1)< n)?(list2+size-1):(n-1);

for(i=list1,j=list2;i< =u1 &&amp;amp;amp; j< =u2;k++)
if(x[i]< =x[j])
sub[k]=x[i++];
else
sub[k]=x[j++];

for(;i< =u1;k++)
sub[k]=x[i++];

for(;j< =u2;k++)
sub[k]=x[j++];

list1=u2+1;
}
for(i=list1;k< n;i++)
sub[k++] = x[i];
for(i=0;i< n;i++)
x[i] =sub[i];
size *= 2;
}
}
/********* OUTPUT **********

Enter The Length Of The Array : 5
Enter Element 1 : 12
Enter Element 2 : 69
Enter Element 3 : 78
Enter Element 4 : 2
Enter Element 5 : 5

│ Sorted Array : │
│2 5 12 69 78 │
*/

4 comments:

Anonymous said...

great work champ
you are helping student

crazy bot said...

good nice dude

pdp said...

Great but Just wanted to say make it well implemented and indented so that it can be easy to read.

Anonymous said...

thankx a lot. i hv no words 2 xpress my hapiness

Your Ad Here