We have already covered Merge Sort for single linked list in our previous post. The merge sort algorithm on doubly linked list works in a similar way, which is by splitting the list into two halves, and then sorting each sublist recursively and finally merging both the sorted list together to get single sorted list.
Just like a normal merge sort algorithm works by breaking a array into two parts, then breaking the two parts further into smaller data set until a data set has only a single data element and we know that a single data element is by default sorted, then we start merging the data elements, eventually getting the sorted list.
The important change here in case of doubly linked list is that we will have to modify the previous pointers of the node also while merging any two sublists.
Implementation in C/C++:
In the code below, we have a structure node which will store data and next and previous pointers. Whenever we implement a Linked List we have to create a node because a linked list is nothing but a list of nodes.
#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 poitner\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;
}
In the code above we have a function split() used for splitting the doubly linked list into two sublist and we are calling it from inside the mergeSort() function and then we are again calling the function mergeSort() on the two sublist, hence this becomes a recursive call.
And at the end we call merge() function to merge the two sublist into one list.
Time Complexity of the Algorithm
The time complexity of this algorithm is same as the time complexity for the merge sort for arrays; i.e. O(nlogn)
If you think the above program can be improved then please do share your code in the comment section below.
You may also like:
