Sort a linked list using merge sort

// C Program
// Sort a linked list using merge sort

#include <stdio.h>
 //for malloc function
#include <stdlib.h>

//Create structure
struct Node
{
	int data;
	struct Node *next;
};
//Add new node at end of linked list 
void insert(struct Node **head, int value)
{
	//Create dynamic node
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	if (node == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		node->data = value;
		node->next = NULL;
		if ( *head == NULL)
		{
			*head = node;
		}
		else
		{
			struct Node *temp = *head;
			//find last node
			while (temp->next != NULL)
			{
				temp = temp->next;
			}
			//add node at last possition
			temp->next = node;
		}
	}
}
//Display linked list element
void display(struct Node *head)
{
	if (head == NULL)
	{
		printf("Empty linked list");
		return;
	}
	struct Node *temp = head;
	printf("\n Linked List :");
	while (temp != NULL)
	{
		printf("  %d", temp->data);
		temp = temp->next;
		if (temp == head)
		{
			printf("Loop");
			//When loop existing
			return;
		}
	}
}
//This are returning middle node of given linked list
struct Node *find_middle(struct Node *head, struct Node *tail)
{
	if (head->next == NULL || head == tail)
	{
		return head;
	}
	else
	{
		//Auxiliary variables
		struct Node *low = head;
		struct Node *high = head;
		while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
		{
			//visit to next node
			low = low->next;
			//visit to second next node
			high = high->next->next;
		}
		//This is middle element
		return low;
	}
}
//Merge two sorted list and return its result
struct Node *merge_list(struct Node *list1, struct Node *list2)
{
	if (list1 == NULL)
	{
		//When list1 is empty
		return list2;
	}
	else if (list2 == NULL)
	{
		return list1;
	}
	else
	{
		//Some auxiliary variables
		struct Node *result = NULL;
		struct Node *tail = NULL;
		struct Node *node = NULL;
		// Combine list elements in sorted order
		// This process takes(m+n) time
		// Here m is size of list1
		// And n is size of list2
		while (list1 != NULL || list2 != NULL)
		{
			if (list1 != NULL && list2 != NULL)
			{
				//When both list contain nodes
				if (list1->data < list2->data)
				{
					//When first list element are smallest
					node = list1;
					list1 = list1->next;
				}
				else
				{
					//When second list element are smallest
					node = list2;
					list2 = list2->next;
				}
			}
			else if (list1 != NULL)
			{
				//When first list contain element
				//Get sublist
				node = list1;
				//Set that list1 empty
				list1 = NULL;
			}
			else
			{
				//When second list contain element
				//get sublist
				node = list2;
				list2 = NULL;
			}
			if (result == NULL)
			{
				//When get first node of resultant list
				result = node;
			}
			else
			{
				//Add node at end of resultant list
				tail->next = node;
			}
			tail = node;
		}
		return result;
	}
}
//Perform merge sort in given linked list
struct Node *merge_sort(struct Node *front, struct Node *tail)
{
	if (front == NULL || front == tail || front->next == NULL)
	{
		//When have zero or one node
		return front;
	}
	//Find the relative middle node
	struct Node *middle = find_middle(front, tail);
	//Get the right side sublist
	struct Node *right_nodes = merge_sort(middle->next, tail);
	//Separate linked list elements
	middle->next = NULL;
	//Get the left side sublist
	struct Node *left_nodes = merge_sort(front, middle);
	//sorted merge in two list
	return merge_list(left_nodes, right_nodes);
}
int main()
{
	struct Node *head = NULL;
	//Create linked list
	insert( &head, 9);
	insert( &head, 5);
	insert( &head, 7);
	insert( &head, 11);
	insert( &head, 3);
	insert( &head, 13);
	insert( &head, 4);
	insert( &head, 8);
	insert( &head, 2);
	printf("\n Before Sort ");
	display(head);
	head = merge_sort(head, NULL);
	printf("\n After Sort ");
	display(head);
	return 0;
}

Output

 Before Sort
 Linked List :  9  5  7  11  3  13  4  8  2
 After Sort
 Linked List :  2  3  4  5  7  8  9  11  13