Merge sort using ‘c’
Merge sort
is a divide-and-conquer sorting algorithm that divides the input array into
smaller halves, recursively sorts them, and then merges the sorted halves to
produce a sorted output. The key idea is to repeatedly divide the array until
it consists of single elements, and then merge them back together in sorted
order.
Here's the
step-by-step process of the merge sort algorithm:
1. Divide
the unsorted array into two halves, roughly equal in size.
2. Recursively
sort the left and right halves of the array.
3. Merge
the two sorted halves back together to obtain a single sorted array.
The merge
operation is the critical step in the merge sort algorithm. It takes two sorted
arrays and merges them into a single sorted array. Here's how it works:
1. Create
an empty auxiliary array to store the merged result.
2. Compare
the first elements of the two sorted arrays.
3. Select
the smaller element and add it to the auxiliary array.
4. Move the
corresponding pointer (index) in the array from which the element was selected
one position ahead.
5. Repeat
steps 3-4 until one of the arrays is exhausted (all elements have been
processed).
6. Copy the
remaining elements from the non-exhausted array to the auxiliary array.
7. The
auxiliary array now contains the merged and sorted elements.
Program:-
#include<stdio.h>
void
partation(int [],int,int);
void
merge(int [],int,int,int);
int main()
{
int a[100],n,i;
printf("enter array size\n");
scanf("%d",&n);
printf("enter array elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
partation(a,0,n-1);
printf("array series after
sorting\n");
for(i=0;i<n;i++)
printf("%d,",a[i]);
return 0;
}
void
partation(int a[100],int lb,int ub)
{
int mid;
if(lb==ub)
return;
mid=(lb+ub)/2;
partation(a,lb,mid);
partation(a,mid+1,ub);
merge(a,lb,mid,ub);
}
void
merge(int a[100],int lb,int mid,int ub)
{
int i,j,temp[30],k=-1,pos;
if(lb>ub)
return;
else
{
i=lb;
j=mid+1;
while(i<=mid&&j<=ub)
{
if(a[i]>a[j])
{
k++;
temp[k]=a[j];
j++;
}
else if(a[i]<a[j])
{
k++;
temp[k]=a[i];
i++;
}
else
{
k++;
temp[k]=a[i];
i++;
k++;
temp[k]=a[j];
j++;
}
}
while(i<=mid)
{
k++;
temp[k]=a[i];
i++;
}
while(j<=ub)
{
k++;
temp[k]=a[j];
j++;
}
for(i=lb,pos=0;pos<=k;pos++,i++)
a[i]=temp[pos];
}
}
Output:-
0 Comments