Program for perform merge sort using linklist

//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