Merge Sort for Doubly Linked List

Introduction

In this article, we will learn how to apply merge sort for doubly linked list.
Merge sort is a sorting algorithm that uses a divide and conquers approach to sort the elements and in doubly linked list each node contains the pointer link to previous as well to the next node in the sequence.

Problem statement for merge sort on doubly linked list

In this problem, we are given a doubly linked list (root node) and are asked to sort it using the merge sort algorithm.

For example

Input:

Output:

Problem Statement Understanding for merge sort on doubly linked list

Let’s try to understand merge sort on doubly linked list with help of an example.

In this problem, we will be given a doubly linked list, and we will have to sort the doubly linked list using Merge Sort.

Let’s suppose the given linked list is:

Now using the merge sort we will sort it to obtain the final sorted linked list:

Merge sort is basically a divide and conquer technique in which, we recursively divide the list into two sub-lists at each step till list size is reduced to one and while backtracking from the recursive call, we have two sorted lists which will be merged together by merge() function in linear time.

The above approach is common to both singly-linked lists and doubly-linked lists. The only difference is that we also have to modify the previous pointer while merging the sorted lists. While merging the doubly linked lists, we have to make sure that the previous pointer points to the previously appended node in the merged list.

Now I think from the above example and explanation it is clear what we have to do in the problem as well as what merge sort is.

Now we will look at approach and algorithm to apply merge sort on doubly linked list.

Approach and Algorithm for applying merge sort on doubly linked list

• Find the middle node.
• Split the list around the middle node.
• Recursively call mergeSort on both sub-lists.
• Merge both sorted sub-lists.

Finding middle node of the list

1. We will maintain a fast pointer and a slow pointer. Initially, both pointers will point to the head of the linked list.
2. Now, we will move the slow pointer by one node and the fast pointer by two nodes at a time.
3. When the fast pointer reaches the end of the list, the slow pointer will point to the middle node. So, we will return slowly.

Merging two sorted linked lists

We will use the merge() function to merge the sorted lists. This function accepts two nodes as parameters, list1(node of the first list) and list2(node of the second list).

• If list1 is null, return list2.
• If list2 is null, return list1.
• If list1 is less than list2 append list1 to the resultant list, else append list2.

Dry Run

Let’s try to visualize it (Visualizing Merge Sort):

Code Implementation

public class Prepbytes {
    static class Node {
        int data;
        Node next;
        Node prev;

        Node() {
        };

        Node(int num) {
            data = num;
            next = null;
            prev = null;
        }
    };

    public static Node sort(Node head) {
        if (head == null) {
            return head;
        }
       if (head.next == null){
            return head;
        }

        head = mergeSort(head);
        return head;
    }

    public static Node mergeSort(Node dnode) {
        if (dnode == null || dnode.next == null) {
            return dnode;
        }

        Node mid = getMidNode(dnode);
        Node next = mid.next;
        mid.next = null;

        Node l1 = mergeSort(dnode);
        Node l2 = mergeSort(next);

        return merge(l1, l2);
    }

    public static Node merge(Node list1, Node list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.data <= list2.data) {
            list1.next = merge(list1.next, list2);
            list1.next.prev = list1;
            list1.prev = null;
            return list1;
        } else {
            list2.next = merge(list1, list2.next);
            list2.next.prev = list2;
            list2.prev = null;
            return list2;
        }
    }

    public static Node getMidNode(Node node) {
        Node slow = node;
        Node fast = node;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(5);
        head.next.next = new Node(4);
        head.next.next.next = new Node(9);
        head.next.next.next.next = new Node(10);
        head.next.next.next.next.next = new Node(6);

        head = sort(head);
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
}

Output

1 4 5 6 9 10

Time Complexity: O(n*log(n)), where n is the number of nodes in the linked list. The merge sort divides the list into two sub-list and the two sub-lists are merged in linear time.

In this blog, we have explained merge sort for doubly linked list. We have provided an overview of merge sort followed by problem statement understanding, and also explained how we can apply merge sort with full approaches and dry run followed by code implementation. To brush up your skills and to explore and learn linked lists more, you can follow this link which is curated by our expert mentors at PrepBytes,Linked List.

FAQs on merge sort for doubly linked list

1. Which sorting algorithm is most suitable for doubly linked lists?

For sorting the doubly linked list using the selection sort technique.

2. What is the time complexity of using bubble sort for sorting doubly linked lists?

O(n^2) will be used for sorting doubly linked list using bubble sort.

3. What are the advantages of a doubly linked list?
• We can iterate in both directions.
• Reversal becomes easy.
• We can delete a node easily as we have to access its previous node.