## Sorting – Merge Sort

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();
}

Radix Sort sorts the number in scans equal to the number of digits of maximum number.

eg.  45, 3, 235, 89, 150, then maximum scans = 3.

Thus radix sort operates three times.

Radix sort uses 10 queues to sort the given numbers.

• Begin with least significant digit, ending with most significant digit.
• Fetch a number from the array and place it in one of the queues depending upon its value say 2 means it is placed in node[2].  If a number already exists at that position than the correct ordered position for the new number is determined.
• Retrieve these elements from the queue from 0 to n back into array.
• Repeat this process till most significant bit.
• Display the array which is finally sorted.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 5

struct queue
{int info;
struct queue *next;
}*node[10]={NULL};

struct queue *front=NULL,*rear=NULL;
struct queue *create()
{
struct queue *temp=(struct queue*)malloc(sizeof(struct queue));
if(temp==NULL)
{printf(“\nMemory Allocation Error!”);
exit(1);
}
return temp;
}

struct queue *makenode(int num)
{
struct queue *temp=create();
temp->info=num;
temp->next=NULL;
return temp;
}
struct queue *insert(struct queue *s,int num)
{
struct queue *ptr=s;
struct queue *temp=makenode(num);
if(s==NULL)
s=temp;
else
{while((ptr->next->info<=num) && (ptr->next!=NULL))
ptr=ptr->next;
if(temp->info<ptr->info)
{temp->next=ptr;
s=temp;
}
else
{temp->next=ptr->next;
ptr->next=temp;
}
}
return s;
}

int digits_count(int num)
{
int rmdr,quot,ct=0;
quot=num/10;
rmdr=num%10;
ct++;
while(quot!=0)
{
num=quot;
quot=num/10;
rmdr=num%10;
ct++;
}
return ct;
}

int max_element(int arr[],int n)
{
int max,i;
max=arr[0];
for(i=1;i<n;i++)
{if(arr[i]>max)
max=arr[i];
}
return max;
}

int return_ith_digit(int num,int pos)
{
int i, ndigits, rmdr;
ndigits = digits_count(num);
if(pos>ndigits)
return 0;
rmdr=num%10;
for(i=0;i<pos;i++)
{
num=num/10;
rmdr=num%10;
}
return rmdr;
}

{
int i,j,digits,max,y;
int k=0,p=0;
max=max_element(arr,n);
digits = digits_count(max);
for(i=0;i<digits;i++)
{
for(j=0;j<n;j++)
{
y=return_ith_digit(arr[j],i);
node[y]=insert(node[y],arr[j]);
}
for(p=0;p<10;p++)
{
while(node[p]!=NULL)
{
arr[k++]=node[p]->info;
printf(“%d->”,node[p]->info);
node[p]=node[p]->next;
}
}
printf(“\b\b “);
}
}
void main()
{
int arr[MAX],i,n;
clrscr();
printf(“\nEnter total number of elements?”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
getch();
}

x Close