Sorting – Merge Sort
Merging:- Merging is the process of combining two or more sorted files into a third sorted file. An example of a routine that accepts two sorted arrays a and b of n1 and n2 elements respectively and merges them into a third array c containing n3 (n1+n2) elements.
Steps for Merge Sort:
- Divide the file n subfiles of size 1 and merge adjacent pair of files.
- We then have approximately n/2 files of size 2.
- Repeat this process until there is only file of size n.
- An auxillary array aux, of size n is required to hold the results of merging two subarrays of x. The variable size contains the size of the subarrays being merged. Since at any time the two files being merged are both subarrays of x, lower and upper bounds are required to indicate the subfiles of x being merged. l1 and u1 represents the lower and upper bounds of the first file and l2 and u2 represents the lower and upper bounds of the second file respectively. i and j are used to reference elements of the source files being merged and k indexes the destination file aux.
Program to merge two sorted arrays to result in another sorted array:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 10
int checksort(int arr[],int n)
{
int i,j,temp,flag=1;
for(i=0;i<n-1;i++)
{for(j=i+1;j<n;j++)
{if(arr[i]>arr[j])
{flag=0;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
return flag;
}
void mergearr(int a[], int b[], int c[], int n1,int n2,int n3)
{
int al,bl,cl,ah,bh,ch,i;/*l for low, h for high*/
ah=n1-1;
bh=n2-1;
ch=n3-1;
if(n1+n2!=n3)
{printf(“\nArray bounds not proper!”);
exit(1);
}
al=0;
bl=0;
for(i=0;al<=ah && bl<=bh;i++)
{if(a[al]<b[bl])
c[i]=a[al++];
else
c[i]=b[bl++];
}
while(al<=ah)
c[i++]=a[al++];
while(bl<=bh)
c[i++]=b[bl++];
}
void main()
{
int a1[MAX],a2[MAX],a3[MAX],n1,n2,n3,i;
clrscr();
printf(“\nEnter the size of first array?”);
scanf(“%d”,&n1);
printf(“\nEnter the size of second array?”);
scanf(“%d”,&n2);
printf(“\nEnter elements of first array?”);
for(i=0;i<n1;i++)
{scanf(“%d”,&a1[i]);
}
printf(“\nEnter elements of second array?”);
for(i=0;i<n2;i++)
{scanf(“%d”,&a2[i]);
}
n3=n1+n2;
if(!checksort(a1,n1))
{printf(“\nMerging operates on sorted array.”);
printf(“\nFirst Array you entered is not sorted.”);
printf(“\nSorting array 1….”);
printf(“\nPress any key to continue!”);
getch();
}
if(!checksort(a2,n2))
{printf(“\n\nMerging operates on sorted array.”);
printf(“\nSecond Array you entered is not sorted.”);
printf(“\nSorting array 2….”);
printf(“\nPress any key to continue!”);
getch();
}
printf(“\n\nNow Merging both the sorted arrays…\n”);
mergearr(a1,a2,a3,n1,n2,n3);
printf(“\nMerged sorted array is:”);
for(i=0;i<n3;i++)
printf(“%d\t”,a3[i]);
getch();
}
Program to implement Merge sort:
#include <stdio.h>
#include <conio.h>
#define MAX 10
void mergesort(int x[], int n)
{
int aux[MAX],i,j,k,l1,l2,u1,u2,size;
size=1;/*initially size is 1.*/
while(size<n)
{
l1=0;
k=0;/*k is the index of auxillary array.*/
while((l1+size)<n)
{l2=l1+size;
u1=l2-1;
u2=((l2+size-1)<n)?(l2+size-1):n-1;
for(i=l1,j=l2;i<=u1 && j<=u2;k++)
{if(x[i]<=x[j])
aux[k]=x[i++];
else
aux[k]=x[j++];
}
/*Remaining elements of first array*/
for(;i<=u1;k++)
aux[k]=x[i++];
/*Remaining elements of second array*/
for(;j<=u2;k++)
aux[k]=x[j++];
/*Advance l1 to the start of the next pair of files.*/
l1=u2+1;
}
for(i=l1;k<n;i++)
aux[k++]=x[i];
for(i=0;i<n;i++)
x[i]=aux[i];
size *= 2;
}
}
void main()
{
int array[MAX],i;
clrscr();
printf(“Enter array elements?”);
for(i=0;i<MAX;i++)
scanf(“%d”,&array[i]);
mergesort(array,MAX);
printf(“Sorted elements are: “);
for(i=0;i<MAX;i++)
printf(“%d\t”,array[i]);
getch();
}