C program of Merge Sort For Linked List

#include<stdio.h>
#include<stdlib.h>

struct node
{
	int info;
	struct node *link;
};

struct node *merge_sort(struct node *p);
struct node *divide(struct node *p);
struct node *merge(struct node *p,struct node *q);
void display(struct node *start);
struct node *create_list(struct node *start);
struct node *addatbeg(struct node *start,int data);
struct node *addatend(struct node *start,int data);

main( )
{
	struct node *start=NULL;
	start = create_list(start);
	start = merge_sort(start);
	display(start);
}

struct node *merge_sort(struct node *start)
{
	struct node *start_first, *start_second, *start_merged;
	
	if( start!=NULL && start->link!=NULL )/*if more than one element*/
	{
		start_first = start;
		start_second = divide(start);
		start_first = merge_sort(start_first);
		start_second = merge_sort(start_second);
		start_merged = merge(start_first, start_second);
		return start_merged;
	}
	else
		return start;
}

struct node *divide(struct node *p)
{
	struct node *q, *start_second;
	
	q=p->link->link;
	while(q!=NULL)
	{
		p=p->link;
		q=q->link;
		if(q!=NULL)
			q=q->link;
	}
	start_second = p->link;
	p->link = NULL;
	return start_second;
}

struct node *merge(struct node *p1,struct node *p2)
{
	struct node *start_merged,*q;
	
	if(p1->info <= p2->info)
	{
		start_merged = p1;
		p1 = p1->link;
	}
	else
	{
		start_merged = p2;
		p2 = p2->link;
	}
	
	q = start_merged;
	while( p1!=NULL && p2!=NULL )
	{
		if( p1->info <= p2->info )
		{
			q->link = p1;
			q = q->link;
			p1 = p1->link;
		}
		else
		{
			q->link = p2;
			q = q->link;
			p2 = p2->link;
		}
	}
	
	if(p1!=NULL)
		q->link=p1;
	else
		q->link=p2;
	return start_merged;
}

void display(struct node *start)
{
	struct node *p;
	if(start==NULL)
	{
		printf("List is empty\n");
		return;
	}
	p=start;
	printf("List is :\n");
	while(p!=NULL)
	{
		printf("%d ",p->info);
		p=p->link;
	}
	printf("\n");
}/*End of display() */

struct node *create_list(struct node *start)
{
	int i,n,data;
	printf("Enter the number of nodes : ");
	scanf("%d",&n);
	start=NULL;
	printf("Enter the element to be inserted : ");
	scanf("%d",&data);
	start=addatbeg(start,data);
	for(i=2;i<=n;i++)
	{
		printf("Enter the element to be inserted : ");
		scanf("%d",&data);
		start=addatend(start,data);	
	}
	return start;
}/*End of create_list()*/

struct node *addatbeg(struct node *start,int data)
{
	struct node *tmp;
	tmp=malloc(sizeof(struct node));
	tmp->info=data;
	tmp->link=start;
	start=tmp;
	return start;
}/*End of addatbeg()*/

struct node *addatend(struct node *start,int data)
{
	struct node *p,*tmp;
	tmp=malloc(sizeof(struct node));
	tmp->info=data;
	p=start;
	while(p->link!=NULL)
		p=p->link;
	p->link=tmp;
	tmp->link=NULL;
	return start;
}/*End of addatend()*/