# Merge Sort for Doubly Linked List

## Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort

### Example

Time Complexity : O(nlogn)

## Algorithm

mergeSort()

1. If head is NULL or there is only one element in the linked list then return

2. Else divide the linked list into two halves  ie, splitLL() splits list into list1 and list2

3. Sort the two halves     ie, recursively call mergeSort(list1), mergeSort(list2)

4. Merge the two sorted halves ie, mergeSortedList(list1,list2) does this job

Note : The above algorithm is same as mergeSort for singly linked list, but while merging two lists we need to modify prev pointer also

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LLNode{
int data;
LLNode *next;
LLNode *prev;
};
//Prototypes
LLNode* mergeSortedLists(LLNode* list1, LLNode* list2);
void splitLL(LLNode* head, LLNode** list1, LLNode** list2);

//Main function, which will sort the lists
{
LLNode* list1;
LLNode* list2;
/* Base case -- length 0 or 1 */
{
return;
}

// Split list(head) into 'list1' and 'list2' sublists

/* Recursively sort the sublists */
mergeSort(&list1);
mergeSort(&list2);
//merge the two sorted lists together
}
//Merge the two sorted lists
LLNode* mergeSortedLists(LLNode* list1, LLNode* list2)
{
//display(&list1);
//cout<<(list1->data);
LLNode* result = NULL;

/* Base cases */
if (list1 == NULL)
return(list2);
else if (list2==NULL)
return(list1);

/* Pick either list1 or list2, and recur */
if (list1->data <= list2->data)
{
list1->next = mergeSortedLists(list1->next,list2);
list1->next->prev = list1;
list1->prev = NULL;
return list1;
}
else
{
list2->next = mergeSortedLists(list1,list2->next);
list2->next->prev = list2;
list2->prev = NULL;
return list2;
}
}

//split the nodes into two halves
LLNode** list1, LLNode** list2)
{
LLNode* fast;
LLNode* slow;
{
/* length < 2 cases */
*list2 = NULL;
}
else
{

// Move 'fast' two nodes, and move 'slow' one node //
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}

/* 'slow' is before the midpoint in the list, so split it in two
at that point. */
*list2 = slow->next;
slow->next = NULL;
}
}
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next= curr->prev = NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

//Will print the list
{

while(head!=NULL) //till the list ends (NULL marks ending of list)
{
}
cout<<"Forward Traversal using next pointer"<<endl;
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
cout<<temp->data<<" ->";

temp=temp->prev; //move to next node
}
cout<<"Backward Traversal using prev pointer"<<endl;
//O(number of nodes)
cout<<endl;
}

int main()
{

LLNode *head = NULL; //initial list has no elements

cout<<"\nCurrent List is :-\n";