# Program for merge sort on doubly linked list

# A node of the doubly linked list
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None


class DoublyLinkedList:
  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 second 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
  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):
    new_node = Node(new_data)
    new_node.next = self.head

    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 pointer")
    while(node is not None):
      print (node.data, ", ", end='')
      temp = node
      node = node.next

    print ("\nBackward Traversal using prev pointer")
    while(temp):
      print (temp.data, ", ", end='')
      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 ("Doubly Linked List after sorting")
dll.printList(dll.head)
