Merge Sort is a sorting algorithm which works by dividing an array into smaller subarrays,sorting every sub array,and then merging the sorted subarrays back together to form form the final sorted array .This process works as divide and conquer method
Algorithm:
MERGE_SORT(arr,beg,end)
if beg<end
set mid=(beg+end)/2
MERGE_SORT(arr,beg,mid)
MERGE_SORT(arr,mid+1,end)
MERGE(arr,beg,mid,end)
end of if
END MERGE_SORT
WORKING PROCEDURE:
let the elements of array are
12 31 25 8 32 17 40 42
As there are 8 elements in the array so program have to divide as
12 31 25 8
and
32 17 40 42
then program have to divide again as
12 31
25 8
32 17
40 42
again divide in single
12 31 25 8 32 17 40 42
then merge two sorted array
8 12 25 31
and
17 32 40 42
that makes
8 12 17 25 31 32 40 42
Implementtion
#include<stdio.h>
void merge(int a[],int beg,int mid,int end)
{
int i,j,k;
int n1=mid-beg-1;
int n2=end-mid;
int LeftArray[n1];
int RightArray[n2];
for(int i=0;i<n1;i++)
LeftArray[i]=a[beg+i];
for(int j=0;j<n2;j++)
RightArray[j]=a[mid+1+j];
i=0;
j=0;
k=beg;
while(i<n1 && j<n2)
{
if(LeftArray[i]<=RightArray[j])
{
a[k]=LeftArray[i];
i++;
}
else
{
a[k]=RightArray[j];
j++;
}
k++;
}
while(i<n1)
{
a[k]=LeftArray[i];
i++;
k++;
}
while(j<n2)
{
a[k]=RightArray[j];
j++;
k++;
}
}
void mergeSort(int a[],int beg,int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
/* Function to print the array */
void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int a[50],n,i;
printf("enter the size of th array:");
scanf("%d",&n);
{
printf("the array elements :",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
}
printf("before sorting array elements");
printArray(a ,n);
mergeSort(a, 0, n-1);
printf("after sorting elements");
printArray(a, n);
return 0;
}
0 Comments