merge_sort_dll.c

// C program for merge sort on doubly linked list
// Time complexity is the same as time complexity of
// merge sort of arrays O(n log n). Space complexity
// is constant 0(1).
#include<stdio.h>
#include<stdlib.h>
struct Node
{
	int data;
	struct Node *next, *prev;
};

struct Node *split(struct Node *head);

// Function to merge two linked lists
struct Node *merge(struct Node *first, struct Node *second)
{
	// If first linked list is empty
	if (!first)
		return second;

	// If second linked list is empty
	if (!second)
		return first;

	// Pick the smaller value
	if (first->data < second->data)
	{
		first->next = merge(first->next,second);
		first->next->prev = first;
		first->prev = NULL;
		return first;
	}
	else
	{
		second->next = merge(first,second->next);
		second->next->prev = second;
		second->prev = NULL;
		return second;
	}
}

// Function to do merge sort
struct Node *mergeSort(struct Node *head)
{
	if (!head || !head->next)
		return head;
	struct Node *second = split(head);

	// Recur for left and right halves
	head = mergeSort(head);
	second = mergeSort(second);

	// Merge the two sorted halves
	return merge(head,second);
}

// A utility function to insert a new node at the
// beginning of doubly linked list
void insert(struct Node **head, int data)
{
	struct Node *temp =
		(struct Node *)malloc(sizeof(struct Node));
	temp->data = data;
	temp->next = temp->prev = NULL;
	if (!(*head))
		(*head) = temp;
	else
	{
		temp->next = *head;
		(*head)->prev = temp;
		(*head) = temp;
	}
}

// A utility function to print a doubly linked list in
// both forward and backward directions
void print(struct Node *head)
{
	struct Node *temp = head;
	printf("Forward Traversal using next pointer\n");
	while (head)
	{
		printf("%d ",head->data);
		temp = head;
		head = head->next;
	}
	printf("\nBackward Traversal using prev pointer\n");
	while (temp)
	{
		printf("%d ", temp->data);
		temp = temp->prev;
	}
}

// Utility function to swap two integers
void swap(int *A, int *B)
{
	int temp = *A;
	*A = *B;
	*B = temp;
}

// Split a doubly linked list (DLL) into 2 DLLs of
// half sizes
struct Node *split(struct Node *head)
{
	struct Node *fast = head,*slow = head;
	while (fast->next && fast->next->next)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	struct Node *temp = slow->next;
	slow->next = NULL;
	return temp;
}

// Driver program
int main(void)
{
	struct Node *head = NULL;
	insert(&head,5);
	insert(&head,20);
	insert(&head,4);
	insert(&head,3);
	insert(&head,30);
	insert(&head,10);
	head = mergeSort(head);
	printf("\n\nLinked List after sorting\n");
	print(head);
	return 0;
}