C program for merge sorting, using linked list: Creating two linked lists & merge them using Merge sort.

#include<stdio.h>                                           //for standard input/output functions
#include<conio.h>                                          //for console input/output functions

struct node
{
int info;
struct node *next;
}*front = NULL,*front1=NULL,*front2=NULL;      //creating 3 node's pointer variable
 //with initial value NULL, as empty list
 
void insert()                                                             //Function to insert the list item,  
{
struct node *t,*q;
int item;
t = (struct node *)malloc(sizeof(struct node));   //To reserve the memory space to node's element
 printf("Input the item value to be added in the queue : ");
scanf("%d",&item);                                            //user inputs the integer data
 t->info = item;
if( front == NULL )                                              //If the list is still empty
 {
front=t;
front->next=NULL;
}
else                                                                         //If the list is not empty 
{
q = front;
while( q->next!= NULL )
q=q->next;
t->next = q->next;
q->next = t;
}
}

void insert1()                      //Function to insert the list item,
{
struct node *t,*q;
int item;
t = (struct node *)malloc(sizeof(struct node)); //To reserve the memory space to node's element
printf("Input the item value to be added in the queue : ");
scanf("%d",&item);                                         //user inputs the integer data
t->info = item;
if( front == NULL )                                           //if the list is empty
 {
front=t;
front->next=NULL;
}
else                                                                     //if the list is not empty 
{
q = front;
while( q->next!= NULL )
q=q->next;
t->next = q->next;
q->next = t;
}
}

void m1_sort(struct node *t)          //for internal use in function m_sort()
 { 
struct node *tt;
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=t;
}

void m_sort()                                   //for sorting the list & merging
 {
struct node *t1,*t,*temp,*tt;
t=front;
t1=front1;
while(t!=NULL||t1!=NULL)         //for traversing the list till the occurrence of NULL element  
{
if((t->info)<(t1->info))
{
temp=(struct node*)malloc(sizeof(struct node));
temp->info=t->info;
temp->next=NULL;
if(front2==NULL)
front2=temp;
else
{
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=temp;
}
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
temp->info=t1->info;
temp->next=NULL;
if(front2==NULL)
front2=temp;
else
{
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=temp;
}
}
t=t->next;
t1=t1->next;
}
if(t1!=NULL)
m1_sort(t1);
else if(t!=NULL)
m1_sort(t);
}


void display()                          //to display the list element 
{
struct node *ptr;
ptr = front2;
if(front == NULL)
printf("Queue is empty\n");
else
{ 
printf("Queue is :\n");
printf("Priority Item\n");
while(ptr != NULL)
{
printf("%5d\n",ptr->info);
ptr = ptr->next;
}
}
}


int main()
{
int ch;
while(ch!=4)
{
printf("1.Insert in 1st queue\n");
printf("2.Insert in 2nd queue\n");
printf("3.Display\n");
printf("4. Sort!!\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d", &ch);                       //asking the user choice of the list operation
switch(ch)
{
case 1:
insert();
break;
case 2:
insert1();
break;
case 3:
display();
break;
case 4:
m_sort();
break;
case 5:
exit(1);
default :
printf("Wrong choice\n");
}
}
getche();                                     //for exit the program after a keystroke
return 0;
}