//program for perform merge sort using linklist
//writter : kartik
//27-4-11
#include<stdio.h>
#include<conio.h>
struct linklist
{
int info;
struct linklist *next;
}*start=NULL,*first=NULL,*start2,*temp,*node,*last;
typedef struct linklist lk;
void insert(lk **);
void disp(lk **);
void mergesort();
void main()
{
int ch;
char con,cn;
clrscr();
do
{
printf("\n***********************************************");
printf("\n K@rtik's Merge sort");
printf("\n***********************************************");
printf("\n 1. insert sorting data:");
printf("\n 2. display");
printf("\n 3. perform mergeing sort");
printf("\n================================================");
printf("\nenter ur choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n enter data for 1st linklist");
do
{
insert(&start);
fflush(0);
printf("\n do u wnt to insert more(y/n):");
scanf("%c",&cn);
}while(cn=='y');
printf("\n enter data for 2nd linklist");
do
{
insert(&first);
fflush(0);
printf("\n do u wnt to insert more(y/n):");
scanf("%c",&cn);
}while(cn=='y');
break;
case 2:
printf("\n*********>display data of 1st linklist..........");
disp(&start);
printf("\n*********>display data of 2nd linklist..........");
disp(&first);
break;
case 3:
mergesort();
break;
default:
printf("\n==> u must i/p 1 to 3 onlly.....");
}
fflush(0);
printf("\n do u wnt to con(y/n):");
scanf("%c",&con);
}while(con=='y');
getch();
}
void insert(lk **head)
{
lk *node=(lk *)malloc(sizeof(lk));
int item;
printf("\nenter item:");
scanf("%d",&item);
if((*head)==NULL)
{
(*head)=(lk *)malloc(sizeof(lk));
(*head)->info=item;
(*head)->next=NULL;
}
else
{
lk *temp=(*head);
while(temp->next!=NULL)
temp=temp->next;
node->info=item;
temp->next=node;
node->next=NULL;
}
}
void disp(lk **head)
{
lk *temp=(*head);
printf("\n");
if((*head)==NULL)
printf("\n linklist is empty");
else
{
while(temp)
{
printf("%3d",temp->info);
temp=temp->next;
}
}
}
void mergesort()
{
lk *tmp1;
lk *tmp2;
lk (*start2)=(lk *)malloc(sizeof(lk));
tmp1=start;
tmp2=first;
start2=NULL;
while((tmp1) && (tmp2))
{
temp=(lk *)malloc(sizeof(lk));
temp->next=NULL;
if(tmp1->info < tmp2->info)
{
temp->info=tmp1->info;
tmp1=tmp1->next;
}
else if(tmp1->info > tmp2->info)
{
temp->info=tmp2->info;
tmp2=tmp2->next;
}
if(start2==NULL)
{printf("\n NULL");
start2=temp;
}
else
node->next=temp;
node=temp;
last=temp;
}//end of while loop*/
while(tmp1!=NULL)
{
temp=(lk *)malloc(sizeof(lk));
temp->next=NULL;
temp->info=tmp1->info;
tmp1=tmp1->next;
node->next=temp;
node=temp;
last=temp;
}
while(tmp2!=NULL)
{
temp=(lk *)malloc(sizeof(lk));
temp->next=NULL;
temp->info=tmp2->info;
tmp2=tmp2->next;
node->next=temp;
node=temp;
last=temp;
}
printf("\n ***** after merging sort:");
disp(&start2);
}
----------------------------
RAJ SOLUTION'S
www.rajsolution.com
www.sahinraj.blogspot.com
