Merge Sort for Doubly Linked List

Last Updated : 22 Feb, 2023

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}.

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.

C++

// C++ program for merge sort on doubly linked list 
#include <bits/stdc++.h>
using namespace std;
class Node 
{ 
    public:
    int data; 
    Node *next, *prev; 
}; 
 
Node *split(Node *head); 
 
// Function to merge two linked lists 
Node *merge(Node *first, 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 
Node *mergeSort(Node *head) 
{ 
    if (!head || !head->next) 
        return head; 
    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(Node **head, int data) 
{ 
    Node *temp = new 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(Node *head) 
{ 
    Node *temp = head; 
    cout<<"Forward Traversal using next pointer\n"; 
    while (head) 
    { 
        cout << head->data << " "; 
        temp = head; 
        head = head->next; 
    } 
    cout  << "\nBackward Traversal using prev pointer\n"; 
    while (temp) 
    { 
        cout << 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 
Node *split(Node *head) 
{ 
    Node *fast = head,*slow = head; 
    while (fast->next && fast->next->next) 
    { 
        fast = fast->next->next; 
        slow = slow->next; 
    } 
    Node *temp = slow->next; 
    slow->next = NULL; 
    return temp; 
} 
 
// Driver program 
int main(void) 
{ 
    Node *head = NULL; 
    insert(&head, 5); 
    insert(&head, 20); 
    insert(&head, 4); 
    insert(&head, 3); 
    insert(&head, 30); 
    insert(&head, 10); 
    head = mergeSort(head); 
    cout << "Linked List after sorting\n"; 
    print(head); 
    return 0; 
}
 
// This is code is contributed by rathbhupendra

C

// C program for merge sort on doubly linked list
#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 pointer\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;
}

Java

// Java program to implement merge sort in singly linked
// list Linked List Class
import java.util.*;
import java.io.*;
 
public class LinkedList {
 
    static Node head; // head of list
 
    /* Node Class */
    static class Node {
 
        int data;
        Node next, prev;
 
        // Constructor to create a new node
        Node(int d)
        {
            data = d;
            next = prev = null;
        }
    }
 
    void print(Node node)
    {
        Node temp = node;
        System.out.println(
            "Forward Traversal using next pointer");
        while (node != null) {
            System.out.print(node.data + " ");
            temp = node;
            node = node.next;
        }
        System.out.println(
            "\nBackward Traversal using prev pointer");
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.prev;
        }
    }
 
    // Split a doubly linked list (DLL) into 2 DLLs of
    // half sizes
    Node split(Node head)
    {
        Node fast = head, slow = head;
        while (fast.next != null
               && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        Node temp = slow.next;
        slow.next = null;
        return temp;
    }
 
    Node mergeSort(Node node)
    {
        if (node == null || node.next == null) {
            return node;
        }
        Node second = split(node);
 
        // Recur for left and right halves
        node = mergeSort(node);
        second = mergeSort(second);
 
        // Merge the two sorted halves
        return merge(node, second);
    }
 
    // Function to merge two linked lists
    Node merge(Node first, Node second)
    {
        // If first linked list is empty
        if (first == null) {
            return second;
        }
 
        // If second linked list is empty
        if (second == null) {
            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;
        }
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
 
        LinkedList list = new LinkedList();
        list.head = new Node(10);
        list.head.next = new Node(30);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);
        list.head.next.next.next.next = new Node(20);
        list.head.next.next.next.next.next = new Node(5);
 
        Node node = null;
        node = list.mergeSort(head);
        System.out.println("Linked list after sorting :");
        list.print(node);
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Program for merge sort on doubly linked list
 
# A node of the doubly 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 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 right 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 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 ("Linked List after sorting")
dll.printList(dll.head)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to implement merge 
// sort in singly linked list 
 
using System; 
 
// Linked List Class 
public class LinkedList 
{ 
 
    Node head; // head of list 
 
    /* Node Class */
    class Node 
    { 
 
        public int data; 
        public Node next, prev; 
 
        // Constructor to create a new node 
        public Node(int d) 
        { 
            data = d; 
            next = prev = null; 
        } 
    } 
 
    void print(Node node)
    { 
        Node temp = node; 
        Console.WriteLine("Forward Traversal" + 
                          "using next pointer"); 
        while (node != null) 
        { 
            Console.Write(node.data + " "); 
            temp = node; 
            node = node.next; 
        } 
        Console.WriteLine("\nBackward Traversal" +
                            "using prev pointer"); 
        while (temp != null) 
        { 
            Console.Write(temp.data + " "); 
            temp = temp.prev; 
        } 
    } 
 
    // Split a doubly linked list (DLL) 
    //  into 2 DLLs of half sizes 
    Node split(Node head)
    { 
        Node fast = head, slow = head; 
        while (fast.next != null && 
                fast.next.next != null) 
        { 
            fast = fast.next.next; 
            slow = slow.next; 
        } 
        Node temp = slow.next; 
        slow.next = null; 
        return temp; 
    } 
 
    Node mergeSort(Node node)
    { 
        if (node == null || node.next == null) 
        { 
            return node; 
        } 
        Node second = split(node); 
 
        // Recur for left and right halves 
        node = mergeSort(node); 
        second = mergeSort(second); 
 
        // Merge the two sorted halves 
        return merge(node, second); 
    } 
 
    // Function to merge two linked lists 
    Node merge(Node first, Node second) 
    { 
        // If first linked list is empty 
        if (first == null) { 
            return second; 
        } 
 
        // If second linked list is empty 
        if (second == null) 
        { 
            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; 
        } 
    } 
 
    // Driver code
    public static void Main(String[] args) 
    { 
 
        LinkedList list = new LinkedList(); 
        list.head = new Node(10); 
        list.head.next = new Node(30); 
        list.head.next.next = new Node(3); 
        list.head.next.next.next = new Node(4); 
        list.head.next.next.next.next = new Node(20); 
        list.head.next.next.next.next.next = new Node(5); 
         
        Node node = null; 
        node = list.mergeSort(list.head); 
        Console.WriteLine("Linked list after sorting :"); 
        list.print(node); 
    } 
} 
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program to implement merge sort in singly linked list
 
// Linked List Class
 
     var head ; // head of list
 
    /* Node Class */
     class Node {
 
        // Constructor to create a new node
        constructor(d) {
            this.data = d;
            this.next = this.prev = null;
        }
    }
 
    function print( node) {
         temp = node;
        document.write("Forward Traversal using next pointer<br/>");
        while (node != null) {
            document.write(node.data + " ");
            temp = node;
            node = node.next;
        }
        document.write("<br/>Backward Traversal using prev pointer<br/>");
        while (temp != null) {
            document.write(temp.data + " ");
            temp = temp.prev;
        }
    }
 
    // Split a doubly linked list (DLL) into 2 DLLs of
    // half sizes
    function split( head) {
         fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
         temp = slow.next;
        slow.next = null;
        return temp;
    }
 
    function mergeSort( node) {
        if (node == null || node.next == null) {
            return node;
        }
        var  second = split(node);
 
        // Recur for left and right halves
        node = mergeSort(node);
        second = mergeSort(second);
 
        // Merge the two sorted halves
        return merge(node, second);
    }
 
    // Function to merge two linked lists
    function merge( first,  second) {
        // If first linked list is empty
        if (first == null) {
            return second;
        }
 
        // If second linked list is empty
        if (second == null) {
            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;
        }
    }
 
    // Driver program to test above functions
        head = new Node(10);
        head.next = new Node(30);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(20);
        head.next.next.next.next.next = new Node(5);
 
         node = null;
        node = mergeSort(head);
        document.write("Linked list after sorting :<br/>");
        print(node);
 
// This code is contributed by umadevi9616
</script>

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

Thanks to Goku for providing above implementation in a comment here.

Time Complexity: Time complexity of the above implementation is same as time complexity of MergeSort for arrays. It takes Θ(nLogn) time.
Auxiliary Space: O(1). We are only using constant amount of extra space.

You may also like to see QuickSort for doubly linked list

Suggest improvement

Merge Sort for Linked Lists

Iterative Merge Sort for Linked List

Share your thoughts in the comments

Merge sort in different languages

Variations of Merge Sort

Merge Sort in Linked List

Visualization of Merge Sort

Some problems on Merge Sort

Merge sort in different languages

Variations of Merge Sort

Merge Sort in Linked List

Visualization of Merge Sort

Some problems on Merge Sort

Merge Sort for Doubly Linked List

C++

C

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?