PYTHON Programming-Merge Sort for Doubly Linked List - Searching and Sorting - Merge sort for singly linked list is already discussed. The important change here is to modify the previous pointers also when merging two lists.

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

For example, the following doubly linked list should be changed to 2<->4<->8<->10

**We strongly recommend to minimize your browser and try this yourself first.**

Merge sort for singly linked list is already discussed. The important change here is to modify the previous pointers also when merging two lists.

Below is the implementation of merge sort for doubly linked list.

**Python Programming**

Python

```
# Program for merge sort on doubly linked list
# A node of the doublly linked list
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
# Constructor for empty Doubly Linked List
def __init__(self):
self.head = None
# Function to merge two linked list
def merge(self, first, second):
# If first linked list is empty
if first is None:
return second
# If secon linked list is empty
if second is None:
return first
# Pick the smaller value
if first.data < second.data:
first.next = self.merge(first.next, second)
first.next.prev = first
first.prev = None
return first
else:
second.next = self.merge(first, second.next)
second.next.prev = second
second.prev = None
return second
# Function to do merge sort
def mergeSort(self, tempHead):
if tempHead is None:
return tempHead
if tempHead.next is None:
return tempHead
second = self.split(tempHead)
# Recur for left and righ halves
tempHead = self.mergeSort(tempHead)
second = self.mergeSort(second)
# Merge the two sorted halves
return self.merge(tempHead, second)
# Split the doubly linked list (DLL) into two DLLs
# of half sizes
def split(self, tempHead):
fast = slow = tempHead
while(True):
if fast.next is None:
break
if fast.next.next is None:
break
fast = fast.next.next
slow = slow.next
temp = slow.next
slow.next = None
return temp
# Given a reference to the head of a list and an
# integer,inserts a new node on the front of list
def push(self, new_data):
# 1. Allocates node
# 2. Put the data in it
new_node = Node(new_data)
# 3. Make next of new node as head and
# previous as None (already None)
new_node.next = self.head
# 4. change prev of head node to new_node
if self.head is not None:
self.head.prev = new_node
# 5. move the head to point to the new node
self.head = new_node
def printList(self, node):
temp = node
print "Forward Traversal using next poitner"
while(node is not None):
print node.data,
temp = node
node = node.next
print "\nBackward Traversal using prev pointer"
while(temp):
print temp.data,
temp = temp.prev
# Driver program to test the above functions
dll = DoublyLinkedList()
dll.push(5)
dll.push(20);
dll.push(4);
dll.push(3);
dll.push(30)
dll.push(10);
dll.head = dll.mergeSort(dll.head)
print "Linked List after sorting"
dll.printList(dll.head)
```

**Output:**

Linked List after sorting
Forward Traversal using next pointer
3 4 5 10 20 30
Backward Traversal using prev pointer
30 20 10 5 4 3

**Time Complexity: **Time complexity of the above implementation is same as time complexity of MergeSort for arrays. It takes Θ(nLogn) time.

## Add Comment