Apply Merge Sort for Doubly Linked List in Python

In this tutorial, we’re going to learn how to implement the merge sort technique on a doubly linked list in Python. But first, we need to understand the step by step method to implement our logic and get the sorted array at the end.

First, we need to create a class for the nodes(s) that will constitute the linked list. Next, we’ll create a class for the double linked list where basically we’re going to combine two single linked lists, perform the merge sort operation and then print the resultant sorted list.

Implementing merge sort on Doubly Linked List in Python

See the code below:

class Node: 
  def __init__(self,data): 
    self.data=data; 
    self.next=None;
    self.previous=None;

class DoubleLinkedList:
  def __init__(self): 
    self.start=None;
    
  def merge(self,a,b): 
    if (a==None): 
      return b; 
    if (b==None): 
      return a;
    if (a.data < b.data): 
      a.next=self.merge(a.next,b); 
      a.next.previous=a; 
      a.previous=None;
      return a; 
    else: 
      b.next=self.merge(a,b.next); 
      (b.next).previous=b;
      b.previous=None;
      return b;
  def mergesort(self,head): 
    if (head==None): 
      return head; 
    if (head.next==None): 
      return head; 
    b = self.div(head); 
    head = self.mergesort(head); 
    b = self.mergesort(b);
    return self.merge(head,b); 
 
  def div(self,head): 
    first=last=head; 
    while(True): 
      if (first.next==None): 
        break;
      if ((first.next).next==None): 
        break;
      first=(first.next).next;
      last=last.next;
      
    t=last.next;
    last.next=None;
    return t; 
     
  def insert(self,d):  
    n=Node(d); 
    n.next=self.start; 
 
    if (self.start!=None): 
      self.start.previous=n; 
    self.start=n; 
  
  def display(self,node):	
    t=node;
    while(node!=None): 
      print (node.data); 
      t=node; 
      node=node.next;

ob=DoubleLinkedList();
inp=int(input("Enter the number of nodes you want to enter:"));
for i in range(inp):
        j=int(input("Enter the data of the node:"));
        ob.insert(j);
ob.start=ob.mergesort(ob.start) 
print ("\nDisplaying the double linked list after merge sort (in ascending order):");
ob.display(ob.start);

In this program, the ‘merge(); function merges two single linked lists. ‘mergesort()’ function is where we implement the sorting technique. After the sorting is done, we get the resultant linked list in the ‘div()’ function. Next, we have the ‘insert()’ function for inserting new nodes to our list and ‘display()’ function to print the entire sorted list.

Output generated will be:

Enter the number of nodes you want to enter:4
Enter the data of the node:90
Enter the data of the node:2
Enter the data of the node:5
Enter the data of the node:67

Displaying the double linked list after merge sort (in ascending order):
2
5
67
90

Leave a Reply

Your email address will not be published. Required fields are marked *