Merge Sort using LinkList


#include<stdio.h>
#include<conio.h>
struct node
{
int val;
struct node *next;
};
typedef struct node node;
void main()
{
   int choice;
   node *start;
   node* createnode(node*);
   node* mergesort(node*);
   void printlist(node*);
   start=NULL;
   while(1)
   {
   printf("\nEnter your choice:1.CreateList 2.Sorting 3.Print 4.Exit");
   printf("\nChoice:");
   scanf("%d",&choice);
   switch(choice)
   {
   case 1:start=createnode(start);
          break;
   case 2:start=mergesort(start);
          break;
   case 3:printlist(start);
          break;
   case 4:exit(0);
          break;
   default:printf("\nEnter Correct Choice");
   }
   }
getch();
}

node* makenode(int val)
{
node *nn;
nn=(node*)malloc(sizeof(node));
nn->val=val;
nn->next=NULL;
return nn;
}

node* createnode(node*start)
{
int tmp;
node *nn;
node* last;
last=start;
printf("\nEnter -99 for Stop This Process");
   while(1)
   {
   printf("\nEnter the Val of Node:");
   scanf("%d",&tmp);
   if(tmp==-99)
   break;
   nn=makenode(tmp);
   if(!start)
   start=nn;
   else
   last->next=nn;
   last=nn;
   }
return start;
}

node* divide(node *start)
{
node *start2=NULL,*prev,*ptr;
if(!start)
return;
if(start->next)
{ prev=start;
  ptr=start->next->next;
}
    while(ptr)
    {
    prev=prev->next;
    ptr=ptr->next;
    if(ptr)
    ptr=ptr->next;
    }
    start2=prev->next;
    prev->next=NULL;
    return start2;
}

node* merge(node*nn,node*start)
{
    node *start3,*last3,*tmp;
    start3=last3=NULL;
    while(nn&&start)
    {
        if(nn->val<start->val)
        {
          tmp=nn;
          nn=nn->next;
        }
        else
        { tmp=start;
          start=start->next;
        }
        if(!start3)
        start3=tmp;
        else
        last3->next=tmp;
        last3=tmp;
    }
    if(nn)
    {
        if(!start3)
        start3=nn;
        else
        last3->next=nn;
    }
    if(start)
    {
        if(!start3)
        start3=start;
        else
        last3->next=start;
    }
    return start3;

}
node* mergesort(node* start)
{
  node *nn;
  if(start->next)
  {
  nn=divide(start);
  start=mergesort(start);
  nn=mergesort(nn);
  start=merge(nn,start);
  }
  return start;
}

void printlist(node *start)
{
if(!start)
return;
printf("\nSorted List:");
while(start)
{
    printf("%d-->",start->val);
    start=start->next;
}
printf("End");
}


Before Sorting





















After Sorting











No comments: