Posted on by Kalkicode
Code Sorting

Merge sort on doubly linked list

Merge sort is a sorting algorithm that works by dividing the input array or linked list into smaller arrays or linked lists, sorting them recursively, and then merging them back together into a single, sorted output.

When applied to a doubly linked list, Merge sort works by dividing the list into two halves and recursively sorting each half. This is done by using a divide-and-conquer approach, where the list is repeatedly divided into smaller sub-lists until each sub-list contains only one element (which is already sorted).

After each sub-list is sorted, the two halves are merged back together by comparing the first element of each half and selecting the smaller one to be added to the sorted output list. This process is repeated until all elements have been merged back together into a single, sorted doubly linked list.

One advantage of using Merge sort on a doubly linked list is that it is relatively easy to implement because the links between the nodes can be easily adjusted during the merge process. Additionally, Merge sort has a time complexity of O(nlogn) in the worst case, which makes it efficient for large lists.

Program Solution

/*
    C Program 
    Merge sort for doubly linked list
*/
#include <stdio.h>
#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
    int element;
    struct LinkNode *next;
    struct LinkNode *prev;
};
struct DoublyLL
{
    struct LinkNode *front;
    struct LinkNode *rear;
};
// Returns the new linked list
struct DoublyLL *newLinkedList()
{
    struct DoublyLL *dll = (struct DoublyLL *) malloc(sizeof(struct DoublyLL));
    if (dll == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        dll->front = NULL;
        dll->rear = NULL;
    }
    return dll;
}
// Add node at end of Doubly linked list
void addNode(struct DoublyLL *dll, int element)
{
    // Make a new node
    struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
    if (node != NULL)
    {
        // Set node values
        node->element = element;
        node->next = NULL;
        node->prev = NULL;
        if (dll->front == NULL)
        {
            //  When inserting a first node of doubly linked list
            dll->front = node;
            dll->rear = node;
        }
        else
        {
            // Add node at end position
            dll->rear->next = node;
            node->prev = dll->rear;
            dll->rear = node;
        }
    }
    else
    {
        printf("\n Memory Overflow, when creating a new doubly linked list Node\n");
    }
}
// Display element
void printData(struct DoublyLL *dll)
{
    struct LinkNode *node = dll->front;
    printf("\n Linked List of from front to rear \n");
    // Display node of from front to rear
    while (node != NULL)
    {
        printf(" %d →", node->element);
        node = node->next;
    }
    printf(" NULL ");
    printf("\n Linked List of from rear to front \n");
    node = dll->rear;
    // Display node of from rear to front
    while (node != NULL)
    {
        printf(" %d →", node->element);
        node = node->prev;
    }
    printf(" NULL \n");
}
//This are returning middle node of given linked list
struct LinkNode *middleNode(struct LinkNode *head, struct LinkNode *tail)
{
    if (head->next == NULL || head == tail)
    {
        return head;
    }
    else
    {
        //Auxiliary variables
        struct LinkNode *low = head;
        struct LinkNode *high = head;
        while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
        {
            //visit to next node
            low = low->next;
            //visit to second next node
            high = high->next->next;
        }
        //This is middle element
        return low;
    }
}
// Merge two sorted list and return its result
struct LinkNode *mergeList(struct LinkNode *list1, struct LinkNode *list2)
{
    if (list1 == NULL)
    {
        //When list1 is empty
        return list2;
    }
    else if (list2 == NULL)
    {
        return list1;
    }
    else
    {
        // Some auxiliary variables
        struct LinkNode *result = NULL;
        struct LinkNode *tail = NULL;
        struct LinkNode *node = NULL;
        // Combine list elements in sorted order
        // This process takes(m+n) time
        // Here m is size of list1
        // And n is size of list2
        while (list1 != NULL || list2 != NULL)
        {
            if (list1 != NULL && list2 != NULL)
            {
                //When both list contain nodes
                if (list1->element < list2->element)
                {
                    //When first list element are smallest
                    node = list1;
                    list1 = list1->next;
                }
                else
                {
                    //When second list element are smallest
                    node = list2;
                    list2 = list2->next;
                }
            }
            else if (list1 != NULL)
            {
                //When first list contain element
                //Get sublist
                node = list1;
                //Set that list1 empty
                list1 = NULL;
            }
            else
            {
                //When second list contain element
                //get sublist
                node = list2;
                list2 = NULL;
            }
            if (result == NULL)
            {
                //When get first node of resultant list
                result = node;
                node->next = NULL;
                node->prev = NULL;
            }
            else
            {
                //Add node at end of resultant list
                tail->next = node;
                node->prev = tail;
            }
            tail = node;
        }
        return result;
    }
}
// Perform merge sort 
struct LinkNode *mergeSort(struct LinkNode *head, struct LinkNode *tail)
{
    if (head == NULL || head == tail || head->next == NULL)
    {
        // When have zero or one node
        return head;
    }
    // Find the relative middle node
    struct LinkNode *middle = middleNode(head, tail);
    // Get the right sublist
    struct LinkNode *right = mergeSort(middle->next, tail);
    // Separating sublist
    if (middle->next != NULL)
    {
        middle->next->prev = NULL;
    }
    middle->next = NULL;
    //Get the left sublist
    struct LinkNode *left = mergeSort(head, middle);
    // Sorted merge in two list
    return mergeList(left, right);
}
// Handles the request to perform merge sort operation
void sortList(struct DoublyLL *dll)
{
    dll->front = mergeSort(dll->front, dll->rear);
    struct LinkNode *node = dll->front;
    // First last node
    while (node->next != NULL)
    {
        node = node->next;
    }
    // Set new rear node
    dll->rear = node;
}
int main(int argc, char
    const *argv[])
{
    struct DoublyLL *dll = newLinkedList();
    addNode(dll, 5);
    addNode(dll, 3);
    addNode(dll, 7);
    addNode(dll, 1);
    addNode(dll, 9);
    addNode(dll, 6);
    addNode(dll, 2);
    addNode(dll, 8);
    addNode(dll, -2);
    addNode(dll, 0);
    printf("\n Before Sort  ");
    // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
    printData(dll);
    sortList(dll);
    printf("\n After Sort  ");
    //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
    printData(dll);
    return 0;
}

Output

 Before Sort
 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort
 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
/*
    Java Program 
    Merge sort for doubly linked list
*/
class LinkNode
{
    public int element;
    public LinkNode next;
    public LinkNode prev;
    public LinkNode(int element)
    {
        this.element = element;
        this.next = null;
        this.prev = null;
    }
}
class DoublyLL
{
    public LinkNode front;
    public LinkNode rear;
    public DoublyLL()
    {
        this.front = null;
        this.rear = null;
    }
    // Add node at end of Doubly linked list
    public void addNode(int element)
    {
        // Make a new node
        LinkNode node = new LinkNode(element);
        if (this.front == null)
        {
            //  When inserting a first node of doubly linked list
            this.front = node;
            this.rear = node;
        }
        else
        {
            // Add node at end position
            this.rear.next = node;
            node.prev = this.rear;
            this.rear = node;
        }
    }
    // Display element
    public void printData()
    {
        LinkNode node = this.front;
        System.out.print("\n Linked List of from front to rear \n");
        // Display node of from front to rear
        while (node != null)
        {
            System.out.print(" " + node.element + " →");
            node = node.next;
        }
        System.out.print(" NULL ");
        System.out.print("\n Linked List of from rear to front \n");
        node = this.rear;
        // Display node of from rear to front
        while (node != null)
        {
            System.out.print(" " + node.element + " →");
            node = node.prev;
        }
        System.out.print(" NULL \n");
    }
}
public class Sorting
{
    //This are returning middle node of given linked list
    public LinkNode middleNode(LinkNode head, LinkNode tail)
    {
        if (head.next == null || head == tail)
        {
            return head;
        }
        else
        {
            //Auxiliary variables
            LinkNode low = head;
            LinkNode high = head;
            while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
            {
                //visit to next node
                low = low.next;
                //visit to second next node
                high = high.next.next;
            }
            //This is middle element
            return low;
        }
    }
    // Merge two sorted list and return its result
    public LinkNode mergeList(LinkNode list1, LinkNode list2)
    {
        if (list1 == null)
        {
            //When list1 is empty
            return list2;
        }
        else if (list2 == null)
        {
            return list1;
        }
        else
        {
            // Some auxiliary variables
            LinkNode result = null;
            LinkNode tail = null;
            LinkNode node = null;
            // Combine list elements in sorted order
            // This process takes(m+n) time
            // Here m is size of list1
            // And n is size of list2
            while (list1 != null || list2 != null)
            {
                if (list1 != null && list2 != null)
                {
                    //When both list contain nodes
                    if (list1.element < list2.element)
                    {
                        //When first list element are smallest
                        node = list1;
                        list1 = list1.next;
                    }
                    else
                    {
                        //When second list element are smallest
                        node = list2;
                        list2 = list2.next;
                    }
                }
                else if (list1 != null)
                {
                    //When first list contain element
                    //Get sublist
                    node = list1;
                    //Set that list1 empty
                    list1 = null;
                }
                else
                {
                    //When second list contain element
                    //get sublist
                    node = list2;
                    list2 = null;
                }
                if (result == null)
                {
                    //When get first node of resultant list
                    result = node;
                    node.next = null;
                    node.prev = null;
                }
                else
                {
                    //Add node at end of resultant list
                    tail.next = node;
                    node.prev = tail;
                }
                tail = node;
            }
            return result;
        }
    }
    // Perform merge sort 
    public LinkNode mergeSort(LinkNode head, LinkNode tail)
    {
        if (head == null || head == tail || head.next == null)
        {
            // When have zero or one node
            return head;
        }
        // Find the relative middle node
        LinkNode middle = middleNode(head, tail);
        // Get the right sublist
        LinkNode right = mergeSort(middle.next, tail);
        // Separating sublist
        if (middle.next != null)
        {
            middle.next.prev = null;
        }
        middle.next = null;
        //Get the left sublist
        LinkNode left = mergeSort(head, middle);
        // Sorted merge in two list
        return mergeList(left, right);
    }
    // Handles the request to perform merge sort operation
    public void sortList(DoublyLL dll)
    {
        dll.front = mergeSort(dll.front, dll.rear);
        LinkNode node = dll.front;
        // First last node
        while (node.next != null)
        {
            node = node.next;
        }
        // Set new rear node
        dll.rear = node;
    }
    public static void main(String[] args)
    {
        DoublyLL dll = new DoublyLL();
        Sorting task = new Sorting();
        dll.addNode(5);
        dll.addNode(3);
        dll.addNode(7);
        dll.addNode(1);
        dll.addNode(9);
        dll.addNode(6);
        dll.addNode(2);
        dll.addNode(8);
        dll.addNode(-2);
        dll.addNode(0);
        System.out.print("\n Before Sort \n");
        // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
        dll.printData();
        task.sortList(dll);
        System.out.print("\n After Sort \n");
        //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
        dll.printData();
    }
}

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program 
    Merge sort for doubly linked list
*/
class LinkNode
{
    public: int element;
    LinkNode *next;
    LinkNode *prev;
    LinkNode(int element)
    {
        this->element = element;
        this->next = NULL;
        this->prev = NULL;
    }
};
class DoublyLL
{
    public: LinkNode *front;
    LinkNode *rear;
    DoublyLL()
    {
        this->front = NULL;
        this->rear = NULL;
    }
    // Add node at end of Doubly linked list
    void addNode(int element)
    {
        // Make a new node
        LinkNode *node = new LinkNode(element);
        if (this->front == NULL)
        {
            //  When inserting a first node of doubly linked list
            this->front = node;
            this->rear = node;
        }
        else
        {
            // Add node at end position
            this->rear->next = node;
            node->prev = this->rear;
            this->rear = node;
        }
    }
    // Display element
    void printData()
    {
        LinkNode *node = this->front;
        cout << "\n Linked List of from front to rear \n";
        // Display node of from front to rear
        while (node != NULL)
        {
            cout << " " << node->element << " →";
            node = node->next;
        }
        cout << " NULL ";
        cout << "\n Linked List of from rear to front \n";
        node = this->rear;
        // Display node of from rear to front
        while (node != NULL)
        {
            cout << " " << node->element << " →";
            node = node->prev;
        }
        cout << " NULL \n";
    }
};
class Sorting
{
    public:
        //This are returning middle node of given linked list
        LinkNode *middleNode(LinkNode *head, LinkNode *tail)
        {
            if (head->next == NULL || head == tail)
            {
                return head;
            }
            else
            {
                //This is middle element
                //Auxiliary variables
                LinkNode *low = head;
                LinkNode *high = head;
                while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
                {
                    //visit to next node
                    low = low->next;
                    //visit to second next node
                    high = high->next->next;
                }
                return low;
            }
        }
    // Merge two sorted list and return its result
    LinkNode *mergeList(LinkNode *list1, LinkNode *list2)
    {
        if (list1 == NULL)
        {
            //When list1 is empty
            return list2;
        }
        else if (list2 == NULL)
        {
            return list1;
        }
        else
        {
            // Some auxiliary variables
            LinkNode *result = NULL;
            LinkNode *tail = NULL;
            LinkNode *node = NULL;
            // Combine list elements in sorted order
            // This process takes(m+n) time
            // Here m is size of list1
            // And n is size of list2
            while (list1 != NULL || list2 != NULL)
            {
                if (list1 != NULL && list2 != NULL)
                {
                    //When both list contain nodes
                    if (list1->element < list2->element)
                    {
                        //When first list element are smallest
                        node = list1;
                        list1 = list1->next;
                    }
                    else
                    {
                        //When second list element are smallest
                        node = list2;
                        list2 = list2->next;
                    }
                }
                else if (list1 != NULL)
                {
                    //When first list contain element
                    //Get sublist
                    node = list1;
                    //Set that list1 empty
                    list1 = NULL;
                }
                else
                {
                    //When second list contain element
                    //get sublist
                    node = list2;
                    list2 = NULL;
                }
                if (result == NULL)
                {
                    //When get first node of resultant list
                    result = node;
                    node->next = NULL;
                    node->prev = NULL;
                }
                else
                {
                    //Add node at end of resultant list
                    tail->next = node;
                    node->prev = tail;
                }
                tail = node;
            }
            return result;
        }
    }
    // Perform merge sort
    LinkNode *mergeSort(LinkNode *head, LinkNode *tail)
    {
        if (head == NULL || head == tail || head->next == NULL)
        {
            // When have zero or one node
            return head;
        }
        // Find the relative middle node
        LinkNode *middle = this->middleNode(head, tail);
        // Get the right sublist
        LinkNode *right = this->mergeSort(middle->next, tail);
        // Separating sublist
        if (middle->next != NULL)
        {
            middle->next->prev = NULL;
        }
        middle->next = NULL;
        //Get the left sublist
        LinkNode *left = this->mergeSort(head, middle);
        // Sorted merge in two list
        return this->mergeList(left, right);
    }
    // Handles the request to perform merge sort operation
    void sortList(DoublyLL *dll)
    {
        dll->front = this->mergeSort(dll->front, dll->rear);
        LinkNode *node = dll->front;
        // First last node
        while (node->next != NULL)
        {
            node = node->next;
        }
        // Set new rear node
        dll->rear = node;
    }
};
int main()
{
    DoublyLL dll = DoublyLL();
    Sorting task = Sorting();
    dll.addNode(5);
    dll.addNode(3);
    dll.addNode(7);
    dll.addNode(1);
    dll.addNode(9);
    dll.addNode(6);
    dll.addNode(2);
    dll.addNode(8);
    dll.addNode(-2);
    dll.addNode(0);
    cout << "\n Before Sort \n";
    // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
    dll.printData();
    task.sortList(&dll);
    cout << "\n After Sort \n";
    //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
    dll.printData();
    return 0;
}

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
// Include namespace system
using System;
/*
    C# Program 
    Merge sort for doubly linked list
*/
public class LinkNode
{
    public int element;
    public LinkNode next;
    public LinkNode prev;
    public LinkNode(int element)
    {
        this.element = element;
        this.next = null;
        this.prev = null;
    }
}
public class DoublyLL
{
    public LinkNode front;
    public LinkNode rear;
    public DoublyLL()
    {
        this.front = null;
        this.rear = null;
    }
    // Add node at end of Doubly linked list
    public void addNode(int element)
    {
        // Make a new node
        LinkNode node = new LinkNode(element);
        if (this.front == null)
        {
            //  When inserting a first node of doubly linked list
            this.front = node;
            this.rear = node;
        }
        else
        {
            // Add node at end position
            this.rear.next = node;
            node.prev = this.rear;
            this.rear = node;
        }
    }
    // Display element
    public void printData()
    {
        LinkNode node = this.front;
        Console.Write("\n Linked List of from front to rear \n");
        // Display node of from front to rear
        while (node != null)
        {
            Console.Write(" " + node.element + " →");
            node = node.next;
        }
        Console.Write(" NULL ");
        Console.Write("\n Linked List of from rear to front \n");
        node = this.rear;
        // Display node of from rear to front
        while (node != null)
        {
            Console.Write(" " + node.element + " →");
            node = node.prev;
        }
        Console.Write(" NULL \n");
    }
}
public class Sorting
{
    //This are returning middle node of given linked list
    public LinkNode middleNode(LinkNode head, LinkNode tail)
    {
        if (head.next == null || head == tail)
        {
            return head;
        }
        else
        {
            //This is middle element
            //Auxiliary variables
            LinkNode low = head;
            LinkNode high = head;
            while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
            {
                //visit to next node
                low = low.next;
                //visit to second next node
                high = high.next.next;
            }
            return low;
        }
    }
    // Merge two sorted list and return its result
    public LinkNode mergeList(LinkNode list1, LinkNode list2)
    {
        if (list1 == null)
        {
            //When list1 is empty
            return list2;
        }
        else if (list2 == null)
        {
            return list1;
        }
        else
        {
            // Some auxiliary variables
            LinkNode result = null;
            LinkNode tail = null;
            LinkNode node = null;
            // Combine list elements in sorted order
            // This process takes(m+n) time
            // Here m is size of list1
            // And n is size of list2
            while (list1 != null || list2 != null)
            {
                if (list1 != null && list2 != null)
                {
                    //When both list contain nodes
                    if (list1.element < list2.element)
                    {
                        //When first list element are smallest
                        node = list1;
                        list1 = list1.next;
                    }
                    else
                    {
                        //When second list element are smallest
                        node = list2;
                        list2 = list2.next;
                    }
                }
                else if (list1 != null)
                {
                    //When first list contain element
                    //Get sublist
                    node = list1;
                    //Set that list1 empty
                    list1 = null;
                }
                else
                {
                    //When second list contain element
                    //get sublist
                    node = list2;
                    list2 = null;
                }
                if (result == null)
                {
                    //When get first node of resultant list
                    result = node;
                    node.next = null;
                    node.prev = null;
                }
                else
                {
                    //Add node at end of resultant list
                    tail.next = node;
                    node.prev = tail;
                }
                tail = node;
            }
            return result;
        }
    }
    // Perform merge sort
    public LinkNode mergeSort(LinkNode head, LinkNode tail)
    {
        if (head == null || head == tail || head.next == null)
        {
            // When have zero or one node
            return head;
        }
        // Find the relative middle node
        LinkNode middle = middleNode(head, tail);
        // Get the right sublist
        LinkNode right = mergeSort(middle.next, tail);
        // Separating sublist
        if (middle.next != null)
        {
            middle.next.prev = null;
        }
        middle.next = null;
        //Get the left sublist
        LinkNode left = mergeSort(head, middle);
        // Sorted merge in two list
        return mergeList(left, right);
    }
    // Handles the request to perform merge sort operation
    public void sortList(DoublyLL dll)
    {
        dll.front = mergeSort(dll.front, dll.rear);
        LinkNode node = dll.front;
        // First last node
        while (node.next != null)
        {
            node = node.next;
        }
        // Set new rear node
        dll.rear = node;
    }
    public static void Main(String[] args)
    {
        DoublyLL dll = new DoublyLL();
        Sorting task = new Sorting();
        dll.addNode(5);
        dll.addNode(3);
        dll.addNode(7);
        dll.addNode(1);
        dll.addNode(9);
        dll.addNode(6);
        dll.addNode(2);
        dll.addNode(8);
        dll.addNode(-2);
        dll.addNode(0);
        Console.Write("\n Before Sort \n");
        // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
        dll.printData();
        task.sortList(dll);
        Console.Write("\n After Sort \n");
        //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
        dll.printData();
    }
}

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
<?php
/*
    Php Program 
    Merge sort for doubly linked list
*/
class LinkNode
{
    public $element;
    public $next;
    public $prev;

    function __construct($element)
    {
        $this->element = $element;
        $this->next = null;
        $this->prev = null;
    }
}
class DoublyLL
{
    public $front;
    public $rear;

    function __construct()
    {
        $this->front = null;
        $this->rear = null;
    }
    // Add node at end of Doubly linked list
    public  function addNode($element)
    {
        // Make a new node
        $node = new LinkNode($element);
        if ($this->front == null)
        {
            //  When inserting a first node of doubly linked list
            $this->front = $node;
            $this->rear = $node;
        }
        else
        {
            // Add node at end position
            $this->rear->next = $node;
            $node->prev = $this->rear;
            $this->rear = $node;
        }
    }
    // Display element
    public  function printData()
    {
        $node = $this->front;
        echo "\n Linked List of from front to rear \n";
        // Display node of from front to rear
        while ($node != null)
        {
            echo " ". $node->element ." →";
            $node = $node->next;
        }
        echo " NULL ";
        echo "\n Linked List of from rear to front \n";
        $node = $this->rear;
        // Display node of from rear to front
        while ($node != null)
        {
            echo " ". $node->element ." →";
            $node = $node->prev;
        }
        echo " NULL \n";
    }
}
class Sorting
{
    //This are returning middle node of given linked list
    public  function middleNode($head, $tail)
    {
        if ($head->next == null || $head == $tail)
        {
            return $head;
        }
        else
        {
            //This is middle element
            //Auxiliary variables
            $low = $head;
            $high = $head;
            while ($high != null && $high->next != null && $high->next->next != null && $high->next != $tail && $head->next->next != $tail)
            {
                //visit to next node
                $low = $low->next;
                //visit to second next node
                $high = $high->next->next;
            }
            return $low;
        }
    }
    // Merge two sorted list and return its result
    public  function mergeList($list1, $list2)
    {
        if ($list1 == null)
        {
            //When list1 is empty
            return $list2;
        }
        else if ($list2 == null)
        {
            return $list1;
        }
        else
        {
            // Some auxiliary variables
            $result = null;
            $tail = null;
            $node = null;
            // Combine list elements in sorted order
            // This process takes(m+n) time
            // Here m is size of list1
            // And n is size of list2
            while ($list1 != null || $list2 != null)
            {
                if ($list1 != null && $list2 != null)
                {
                    //When both list contain nodes
                    if ($list1->element < $list2->element)
                    {
                        //When first list element are smallest
                        $node = $list1;
                        $list1 = $list1->next;
                    }
                    else
                    {
                        //When second list element are smallest
                        $node = $list2;
                        $list2 = $list2->next;
                    }
                }
                else if ($list1 != null)
                {
                    //When first list contain element
                    //Get sublist
                    $node = $list1;
                    //Set that list1 empty
                    $list1 = null;
                }
                else
                {
                    //When second list contain element
                    //get sublist
                    $node = $list2;
                    $list2 = null;
                }
                if ($result == null)
                {
                    //When get first node of resultant list
                    $result = $node;
                    $node->next = null;
                    $node->prev = null;
                }
                else
                {
                    //Add node at end of resultant list
                    $tail->next = $node;
                    $node->prev = $tail;
                }
                $tail = $node;
            }
            return $result;
        }
    }
    // Perform merge sort
    public  function mergeSort($head, $tail)
    {
        if ($head == null || $head == $tail || $head->next == null)
        {
            // When have zero or one node
            return $head;
        }
        // Find the relative middle node
        $middle = $this->middleNode($head, $tail);
        // Get the right sublist
        $right = $this->mergeSort($middle->next, $tail);
        // Separating sublist
        if ($middle->next != null)
        {
            $middle->next->prev = null;
        }
        $middle->next = null;
        //Get the left sublist
        $left = $this->mergeSort($head, $middle);
        // Sorted merge in two list
        return $this->mergeList($left, $right);
    }
    // Handles the request to perform merge sort operation
    public  function sortList($dll)
    {
        $dll->front = $this->mergeSort($dll->front, $dll->rear);
        $node = $dll->front;
        // First last node
        while ($node->next != null)
        {
            $node = $node->next;
        }
        // Set new rear node
        $dll->rear = $node;
    }
}

function main()
{
    $dll = new DoublyLL();
    $task = new Sorting();
    $dll->addNode(5);
    $dll->addNode(3);
    $dll->addNode(7);
    $dll->addNode(1);
    $dll->addNode(9);
    $dll->addNode(6);
    $dll->addNode(2);
    $dll->addNode(8);
    $dll->addNode(-2);
    $dll->addNode(0);
    echo "\n Before Sort \n";
    // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
    $dll->printData();
    $task->sortList($dll);
    echo "\n After Sort \n";
    //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
    $dll->printData();
}
main();

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
/*
    Node Js Program 
    Merge sort for doubly linked list
*/
class LinkNode
{
    constructor(element)
    {
        this.element = element;
        this.next = null;
        this.prev = null;
    }
}
class DoublyLL
{
    constructor()
    {
        this.front = null;
        this.rear = null;
    }
    // Add node at end of Doubly linked list
    addNode(element)
    {
        // Make a new node
        var node = new LinkNode(element);
        if (this.front == null)
        {
            //  When inserting a first node of doubly linked list
            this.front = node;
            this.rear = node;
        }
        else
        {
            // Add node at end position
            this.rear.next = node;
            node.prev = this.rear;
            this.rear = node;
        }
    }
    // Display element
    printData()
    {
        var node = this.front;
        process.stdout.write("\n Linked List of from front to rear \n");
        // Display node of from front to rear
        while (node != null)
        {
            process.stdout.write(" " + node.element + " →");
            node = node.next;
        }
        process.stdout.write(" NULL ");
        process.stdout.write("\n Linked List of from rear to front \n");
        node = this.rear;
        // Display node of from rear to front
        while (node != null)
        {
            process.stdout.write(" " + node.element + " →");
            node = node.prev;
        }
        process.stdout.write(" NULL \n");
    }
}
class Sorting
{
    //This are returning middle node of given linked list
    middleNode(head, tail)
    {
        if (head.next == null || head == tail)
        {
            return head;
        }
        else
        {
            //This is middle element
            //Auxiliary variables
            var low = head;
            var high = head;
            while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
            {
                //visit to next node
                low = low.next;
                //visit to second next node
                high = high.next.next;
            }
            return low;
        }
    }
    // Merge two sorted list and return its result
    mergeList(list1, list2)
    {
        if (list1 == null)
        {
            //When list1 is empty
            return list2;
        }
        else if (list2 == null)
        {
            return list1;
        }
        else
        {
            // Some auxiliary variables
            var result = null;
            var tail = null;
            var node = null;
            // Combine list elements in sorted order
            // This process takes(m+n) time
            // Here m is size of list1
            // And n is size of list2
            while (list1 != null || list2 != null)
            {
                if (list1 != null && list2 != null)
                {
                    //When both list contain nodes
                    if (list1.element < list2.element)
                    {
                        //When first list element are smallest
                        node = list1;
                        list1 = list1.next;
                    }
                    else
                    {
                        //When second list element are smallest
                        node = list2;
                        list2 = list2.next;
                    }
                }
                else if (list1 != null)
                {
                    //When first list contain element
                    //Get sublist
                    node = list1;
                    //Set that list1 empty
                    list1 = null;
                }
                else
                {
                    //When second list contain element
                    //get sublist
                    node = list2;
                    list2 = null;
                }
                if (result == null)
                {
                    //When get first node of resultant list
                    result = node;
                    node.next = null;
                    node.prev = null;
                }
                else
                {
                    //Add node at end of resultant list
                    tail.next = node;
                    node.prev = tail;
                }
                tail = node;
            }
            return result;
        }
    }
    // Perform merge sort
    mergeSort(head, tail)
    {
        if (head == null || head == tail || head.next == null)
        {
            // When have zero or one node
            return head;
        }
        // Find the relative middle node
        var middle = this.middleNode(head, tail);
        // Get the right sublist
        var right = this.mergeSort(middle.next, tail);
        // Separating sublist
        if (middle.next != null)
        {
            middle.next.prev = null;
        }
        middle.next = null;
        //Get the left sublist
        var left = this.mergeSort(head, middle);
        // Sorted merge in two list
        return this.mergeList(left, right);
    }
    // Handles the request to perform merge sort operation
    sortList(dll)
    {
        dll.front = this.mergeSort(dll.front, dll.rear);
        var node = dll.front;
        // First last node
        while (node.next != null)
        {
            node = node.next;
        }
        // Set new rear node
        dll.rear = node;
    }
}

function main()
{
    var dll = new DoublyLL();
    var task = new Sorting();
    dll.addNode(5);
    dll.addNode(3);
    dll.addNode(7);
    dll.addNode(1);
    dll.addNode(9);
    dll.addNode(6);
    dll.addNode(2);
    dll.addNode(8);
    dll.addNode(-2);
    dll.addNode(0);
    process.stdout.write("\n Before Sort \n");
    // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
    dll.printData();
    task.sortList(dll);
    process.stdout.write("\n After Sort \n");
    //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
    dll.printData();
}
main();

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
#  Python 3 Program 
#  Merge sort for doubly linked list

class LinkNode :
    
    def __init__(self, element) :
        self.element = element
        self.next = None
        self.prev = None
    

class DoublyLL :
    
    def __init__(self) :
        self.front = None
        self.rear = None
    
    #  Add node at end of Doubly linked list
    def addNode(self, element) :
        #  Make a new node
        node = LinkNode(element)
        if (self.front == None) :
            #   When inserting a first node of doubly linked list
            self.front = node
            self.rear = node
        else :
            #  Add node at end position
            self.rear.next = node
            node.prev = self.rear
            self.rear = node
        
    
    #  Display element
    def printData(self) :
        node = self.front
        print("\n Linked List of from front to rear ")
        #  Display node of from front to rear
        while (node != None) :
            print("", node.element ,"→", end = "")
            node = node.next
        
        print(" NULL ", end = "")
        print("\n Linked List of from rear to front ")
        node = self.rear
        #  Display node of from rear to front
        while (node != None) :
            print("", node.element ,"→", end = "")
            node = node.prev
        
        print(" NULL ")
    

class Sorting :
    # This are returning middle node of given linked list
    def middleNode(self, head, tail) :
        if (head.next == None or head == tail) :
            return head
        else :
            # Auxiliary variables
            low = head
            high = head
            while (high != None and high.next != None and high.next.next != None and high.next != tail and head.next.next != tail) :
                # visit to next node
                low = low.next
                # visit to second next node
                high = high.next.next
            
            # This is middle element
            return low
        
    
    #  Merge two sorted list and return its result
    def mergeList(self, list1, list2) :
        if (list1 == None) :
            # When list1 is empty
            return list2
        
        elif(list2 == None) :
            return list1
        else :
            #  Some auxiliary variables
            result = None
            tail = None
            node = None
            #  Combine list elements in sorted order
            #  This process takes(m+n) time
            #  Here m is size of list1
            #  And n is size of list2
            while (list1 != None or list2 != None) :
                if (list1 != None and list2 != None) :
                    # When both list contain nodes
                    if (list1.element < list2.element) :
                        # When first list element are smallest
                        node = list1
                        list1 = list1.next
                    else :
                        # When second list element are smallest
                        node = list2
                        list2 = list2.next
                    
                
                elif(list1 != None) :
                    # When first list contain element
                    # Get sublist
                    node = list1
                    # Set that list1 empty
                    list1 = None
                else :
                    # When second list contain element
                    # get sublist
                    node = list2
                    list2 = None
                
                if (result == None) :
                    # When get first node of resultant list
                    result = node
                    node.next = None
                    node.prev = None
                else :
                    # Add node at end of resultant list
                    tail.next = node
                    node.prev = tail
                
                tail = node
            
            return result
        
    
    #  Perform merge sort 
    def mergeSort(self, head, tail) :
        if (head == None or head == tail or head.next == None) :
            #  When have zero or one node
            return head
        
        #  Find the relative middle node
        middle = self.middleNode(head, tail)
        #  Get the right sublist
        right = self.mergeSort(middle.next, tail)
        #  Separating sublist
        if (middle.next != None) :
            middle.next.prev = None
        
        middle.next = None
        # Get the left sublist
        left = self.mergeSort(head, middle)
        #  Sorted merge in two list
        return self.mergeList(left, right)
    
    #  Handles the request to perform merge sort operation
    def sortList(self, dll) :
        dll.front = self.mergeSort(dll.front, dll.rear)
        node = dll.front
        #  First last node
        while (node.next != None) :
            node = node.next
        
        #  Set new rear node
        dll.rear = node
    

def main() :
    dll = DoublyLL()
    task = Sorting()
    dll.addNode(5)
    dll.addNode(3)
    dll.addNode(7)
    dll.addNode(1)
    dll.addNode(9)
    dll.addNode(6)
    dll.addNode(2)
    dll.addNode(8)
    dll.addNode(-2)
    dll.addNode(0)
    print("\n Before Sort ")
    #  5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
    dll.printData()
    task.sortList(dll)
    print("\n After Sort ")
    # -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
    dll.printData()

if __name__ == "__main__": main()

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
#  Ruby Program 
#  Merge sort for doubly linked list

class LinkNode  
    # Define the accessor and reader of class LinkNode  
    attr_reader :element, :next, :prev
    attr_accessor :element, :next, :prev
 
    
    def initialize(element) 
        self.element = element
        self.next = nil
        self.prev = nil
    end

end

class DoublyLL  
    # Define the accessor and reader of class DoublyLL  
    attr_reader :front, :rear
    attr_accessor :front, :rear
 
    
    def initialize() 
        self.front = nil
        self.rear = nil
    end

    #  Add node at end of Doubly linked list
    def addNode(element) 
        #  Make a new node
        node = LinkNode.new(element)
        if (self.front == nil) 
            #   When inserting a first node of doubly linked list
            self.front = node
            self.rear = node
        else 
            #  Add node at end position
            self.rear.next = node
            node.prev = self.rear
            self.rear = node
        end

    end

    #  Display element
    def printData() 
        node = self.front
        print("\n Linked List of from front to rear \n")
        #  Display node of from front to rear
        while (node != nil) 
            print(" ", node.element ," →")
            node = node.next
        end

        print(" NULL ")
        print("\n Linked List of from rear to front \n")
        node = self.rear
        #  Display node of from rear to front
        while (node != nil) 
            print(" ", node.element ," →")
            node = node.prev
        end

        print(" NULL \n")
    end

end

class Sorting 
    # This are returning middle node of given linked list
    def middleNode(head, tail) 
        if (head.next == nil || head == tail) 
            return head
        else 
            # Auxiliary variables
            low = head
            high = head
            while (high != nil && high.next != nil && high.next.next != nil && high.next != tail && head.next.next != tail) 
                # visit to next node
                low = low.next
                # visit to second next node
                high = high.next.next
            end

            # This is middle element
            return low
        end

    end

    #  Merge two sorted list and return its result
    def mergeList(list1, list2) 
        if (list1 == nil) 
            # When list1 is empty
            return list2
        elsif(list2 == nil) 
            return list1
        else 
            #  Some auxiliary variables
            result = nil
            tail = nil
            node = nil
            #  Combine list elements in sorted order
            #  This process takes(m+n) time
            #  Here m is size of list1
            #  And n is size of list2
            while (list1 != nil || list2 != nil) 
                if (list1 != nil && list2 != nil) 
                    # When both list contain nodes
                    if (list1.element < list2.element) 
                        # When first list element are smallest
                        node = list1
                        list1 = list1.next
                    else 
                        # When second list element are smallest
                        node = list2
                        list2 = list2.next
                    end

                elsif(list1 != nil) 
                    # When first list contain element
                    # Get sublist
                    node = list1
                    # Set that list1 empty
                    list1 = nil
                else 
                    # When second list contain element
                    # get sublist
                    node = list2
                    list2 = nil
                end

                if (result == nil) 
                    # When get first node of resultant list
                    result = node
                    node.next = nil
                    node.prev = nil
                else 
                    # Add node at end of resultant list
                    tail.next = node
                    node.prev = tail
                end

                tail = node
            end

            return result
        end

    end

    #  Perform merge sort 
    def mergeSort(head, tail) 
        if (head == nil || head == tail || head.next == nil) 
            #  When have zero or one node
            return head
        end

        #  Find the relative middle node
        middle = self.middleNode(head, tail)
        #  Get the right sublist
        right = self.mergeSort(middle.next, tail)
        #  Separating sublist
        if (middle.next != nil) 
            middle.next.prev = nil
        end

        middle.next = nil
        # Get the left sublist
        left = self.mergeSort(head, middle)
        #  Sorted merge in two list
        return self.mergeList(left, right)
    end

    #  Handles the request to perform merge sort operation
    def sortList(dll) 
        dll.front = self.mergeSort(dll.front, dll.rear)
        node = dll.front
        #  First last node
        while (node.next != nil) 
            node = node.next
        end

        #  Set new rear node
        dll.rear = node
    end

end

def main() 
    dll = DoublyLL.new()
    task = Sorting.new()
    dll.addNode(5)
    dll.addNode(3)
    dll.addNode(7)
    dll.addNode(1)
    dll.addNode(9)
    dll.addNode(6)
    dll.addNode(2)
    dll.addNode(8)
    dll.addNode(-2)
    dll.addNode(0)
    print("\n Before Sort \n")
    #  5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
    dll.printData()
    task.sortList(dll)
    print("\n After Sort \n")
    # -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
    dll.printData()
end

main()

Output

 Before Sort 

 Linked List of from front to rear 
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL 
 Linked List of from rear to front 
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL 

 After Sort 

 Linked List of from front to rear 
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL 
 Linked List of from rear to front 
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL 
/*
    Scala Program 
    Merge sort for doubly linked list
*/
class LinkNode(var element: Int , var next: LinkNode , var prev: LinkNode)
{
    def this(element: Int)
    {
        this(element, null, null);
    }
}
class DoublyLL(var front: LinkNode , var rear: LinkNode)
{
    def this()
    {
        this(null, null);
    }
    // Add node at end of Doubly linked list
    def addNode(element: Int): Unit = {
        // Make a new node
        var node: LinkNode = new LinkNode(element);
        if (this.front == null)
        {
            //  When inserting a first node of doubly linked list
            this.front = node;
            this.rear = node;
        }
        else
        {
            // Add node at end position
            this.rear.next = node;
            node.prev = this.rear;
            this.rear = node;
        }
    }
    // Display element
    def printData(): Unit = {
        var node: LinkNode = this.front;
        print("\n Linked List of from front to rear \n");
        // Display node of from front to rear
        while (node != null)
        {
            print(" " + node.element + " →");
            node = node.next;
        }
        print(" NULL ");
        print("\n Linked List of from rear to front \n");
        node = this.rear;
        // Display node of from rear to front
        while (node != null)
        {
            print(" " + node.element + " →");
            node = node.prev;
        }
        print(" NULL \n");
    }
}
class Sorting
{
    //This are returning middle node of given linked list
    def middleNode(head: LinkNode, tail: LinkNode): LinkNode = {
        if (head.next == null || head == tail)
        {
            return head;
        }
        else
        {
            //This is middle element
            //Auxiliary variables
            var low: LinkNode = head;
            var high: LinkNode = head;
            while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
            {
                //visit to next node
                low = low.next;
                //visit to second next node
                high = high.next.next;
            }
            return low;
        }
    }
    // Merge two sorted list and return its result
    def mergeList(l1: LinkNode, l2: LinkNode): LinkNode = {
        var list1: LinkNode = l1;
        var list2: LinkNode = l2;
        
        if (list1 == null)
        {
            //When list1 is empty
            return list2;
        }
        else if (list2 == null)
        {
            return list1;
        }
        else
        {
            // Some auxiliary variables
            var result: LinkNode = null;
            var tail: LinkNode = null;
            var node: LinkNode = null;
            // Combine list elements in sorted order
            // This process takes(m+n) time
            // Here m is size of list1
            // And n is size of list2
            while (list1 != null || list2 != null)
            {
                if (list1 != null && list2 != null)
                {
                    //When both list contain nodes
                    if (list1.element < list2.element)
                    {
                        //When first list element are smallest
                        node = list1;
                        list1 = list1.next;
                    }
                    else
                    {
                        //When second list element are smallest
                        node = list2;
                        list2 = list2.next;
                    }
                }
                else if (list1 != null)
                {
                    //When first list contain element
                    //Get sublist
                    node = list1;
                    //Set that list1 empty
                    list1 = null;
                }
                else
                {
                    //When second list contain element
                    //get sublist
                    node = list2;
                    list2 = null;
                }
                if (result == null)
                {
                    //When get first node of resultant list
                    result = node;
                    node.next = null;
                    node.prev = null;
                }
                else
                {
                    //Add node at end of resultant list
                    tail.next = node;
                    node.prev = tail;
                }
                tail = node;
            }
            return result;
        }
    }
    // Perform merge sort
    def mergeSort(head: LinkNode, tail: LinkNode): LinkNode = {
        if (head == null || head == tail || head.next == null)
        {
            // When have zero or one node
            return head;
        }
        // Find the relative middle node
        var middle: LinkNode = this.middleNode(head, tail);
        // Get the right sublist
        var right: LinkNode = this.mergeSort(middle.next, tail);
        // Separating sublist
        if (middle.next != null)
        {
            middle.next.prev = null;
        }
        middle.next = null;
        //Get the left sublist
        var left: LinkNode = this.mergeSort(head, middle);
        // Sorted merge in two list
        return this.mergeList(left, right);
    }
    // Handles the request to perform merge sort operation
    def sortList(dll: DoublyLL): Unit = {
        dll.front = this.mergeSort(dll.front, dll.rear);
        var node: LinkNode = dll.front;
        // First last node
        while (node.next != null)
        {
            node = node.next;
        }
        // Set new rear node
        dll.rear = node;
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var dll: DoublyLL = new DoublyLL();
        var task: Sorting = new Sorting();
        dll.addNode(5);
        dll.addNode(3);
        dll.addNode(7);
        dll.addNode(1);
        dll.addNode(9);
        dll.addNode(6);
        dll.addNode(2);
        dll.addNode(8);
        dll.addNode(-2);
        dll.addNode(0);
        print("\n Before Sort \n");
        // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
        dll.printData();
        task.sortList(dll);
        print("\n After Sort \n");
        //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
        dll.printData();
    }
}

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
/*
    Swift 4 Program 
    Merge sort for doubly linked list
*/
class LinkNode
{
    var element: Int;
    var next: LinkNode? ;
    var prev: LinkNode? ;
    init(_ element: Int)
    {
        self.element = element;
        self.next = nil;
        self.prev = nil;
    }
}
class DoublyLL
{
    var front: LinkNode? ;
    var rear: LinkNode? ;
    init()
    {
        self.front = nil;
        self.rear = nil;
    }
    // Add node at end of Doubly linked list
    func addNode(_ element: Int)
    {
        // Make a new node
        let node: LinkNode? = LinkNode(element);
        if (self.front == nil)
        {
            //  When inserting a first node of doubly linked list
            self.front = node;
            self.rear = node;
        }
        else
        {
            // Add node at end position
            self.rear!.next = node;
            node!.prev = self.rear;
            self.rear = node;
        }
    }
    // Display element
    func printData()
    {
        var node: LinkNode? = self.front;
        print("\n Linked List of from front to rear ");
        // Display node of from front to rear
        while (node  != nil)
        {
            print("", node!.element ,"→", terminator: "");
            node = node!.next;
        }
        print(" NULL ", terminator: "");
        print("\n Linked List of from rear to front ");
        node = self.rear;
        // Display node of from rear to front
        while (node  != nil)
        {
            print("", node!.element ,"→", terminator: "");
            node = node!.prev;
        }
        print(" NULL ");
    }
}
class Sorting
{
    //This are returning middle node of given linked list
    func middleNode(_ head: LinkNode? , _ tail : LinkNode? )->LinkNode?
    {
        if (head!.next == nil || !(head === tail))
        {
            return head;
        }
        else
        {
            //This is middle element
            //Auxiliary variables
            var low: LinkNode? = head;
            var high: LinkNode? = head;
            while (high  != nil && high!.next  != nil
            && high!.next!.next  != nil 
            && !(high!.next  === tail) && !(head!.next!.next  === tail))
            {
                //visit to next node
                low = low!.next;
                //visit to second next node
                high = high!.next!.next;
            }
            return low;
        }
    }
    // Merge two sorted list and return its result
    func mergeList(_ l1:  LinkNode? , _ l2 :  LinkNode? )->LinkNode?
    {
      
        var list1: LinkNode? = l1;
        var list2: LinkNode? = l2;
        if (list1 == nil)
        {
            //When list1 is empty
            return list2;
        }
        else if (list2 == nil)
        {
            return list1;
        }
        else
        {
            // Some auxiliary variables
            var result: LinkNode? = nil;
            var tail: LinkNode? = nil;
            var node: LinkNode? = nil;
            // Combine list elements in sorted order
            // This process takes(m+n) time
            // Here m is size of list1
            // And n is size of list2
            while (list1  != nil || list2  != nil)
            {
                if (list1  != nil && list2  != nil)
                {
                    //When both list contain nodes
                    if (list1!.element < list2!.element)
                    {
                        //When first list element are smallest
                        node = list1;
                        list1 = list1!.next;
                    }
                    else
                    {
                        //When second list element are smallest
                        node = list2;
                        list2 = list2!.next;
                    }
                }
                else if (list1  != nil)
                {
                    //When first list contain element
                    //Get sublist
                    node = list1;
                    //Set that list1 empty
                    list1 = nil;
                }
                else
                {
                    //When second list contain element
                    //get sublist
                    node = list2;
                    list2 = nil;
                }
                if (result == nil)
                {
                    //When get first node of resultant list
                    result = node;
                    node!.next = nil;
                    node!.prev = nil;
                }
                else
                {
                    //Add node at end of resultant list
                    tail!.next = node;
                    node!.prev = tail;
                }
                tail = node;
            }
            return result;
        }
    }
    // Perform merge sort
    func mergeSort(_ head: LinkNode? , _ tail : LinkNode? )->LinkNode?
    {
        if (head == nil || !(head === tail) || head!.next == nil)
        {
            // When have zero or one node
            return head;
        }
        // Find the relative middle node
        let middle: LinkNode? = self.middleNode(head, tail);
        // Get the right sublist
        let right: LinkNode? = self.mergeSort(middle!.next, tail);
        // Separating sublist
        if (middle!.next  != nil)
        {
            middle!.next!.prev = nil;
        }
        middle!.next = nil;
        //Get the left sublist
        let left: LinkNode? = self.mergeSort(head, middle);
        // Sorted merge in two list
        return self.mergeList(left, right);
    }
    // Handles the request to perform merge sort operation
    func sortList(_ dll: DoublyLL? )
    {
        dll!.front = self.mergeSort(dll!.front, dll!.rear);
        var node: LinkNode? = dll!.front;
        // First last node
        while (node!.next  != nil)
        {
            node = node!.next;
        }
        // Set new rear node
        dll!.rear = node;
    }
}
func main()
{
    let dll: DoublyLL = DoublyLL();
    let task: Sorting = Sorting();
    dll.addNode(5);
    dll.addNode(3);
    dll.addNode(7);
    dll.addNode(1);
    dll.addNode(9);
    dll.addNode(6);
    dll.addNode(2);
    dll.addNode(8);
    dll.addNode(-2);
    dll.addNode(0);
    print("\n Before Sort ");
    // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
    dll.printData();
    task.sortList(dll);
    print("\n After Sort ");
    //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
    dll.printData();
}
main();

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
/*
    Kotlin Program 
    Merge sort for doubly linked list
*/
class LinkNode
{
    var element: Int;
    var next: LinkNode ? ;
    var prev: LinkNode ? ;
    constructor(element: Int)
    {
        this.element = element;
        this.next = null;
        this.prev = null;
    }
}
class DoublyLL
{
    var front: LinkNode ? ;
    var rear: LinkNode ? ;
    constructor()
    {
        this.front = null;
        this.rear = null;
    }
    // Add node at end of Doubly linked list
    fun addNode(element: Int): Unit
    {
        // Make a new node
        var node: LinkNode ? = LinkNode(element);
        if (this.front == null)
        {
            //  When inserting a first node of doubly linked list
            this.front = node;
            this.rear = node;
        }
        else
        {
            // Add node at end position
            this.rear?.next = node;
            node?.prev = this.rear;
            this.rear = node;
        }
    }
    // Display element
    fun printData(): Unit
    {
        var node: LinkNode ? = this.front;
        print("\n Linked List of from front to rear \n");
        // Display node of from front to rear
        while (node != null)
        {
            print(" " + node.element + " →");
            node = node.next;
        }
        print(" NULL ");
        print("\n Linked List of from rear to front \n");
        node = this.rear;
        // Display node of from rear to front
        while (node != null)
        {
            print(" " + node.element + " →");
            node = node.prev;
        }
        print(" NULL \n");
    }
}
class Sorting
{
    //This are returning middle node of given linked list
    fun middleNode(head: LinkNode ? , tail : LinkNode ? ): LinkNode ?
    {
        if (head?.next == null || head == tail)
        {
            return head;
        }
        else
        {
            //This is middle element
            //Auxiliary variables
            var low: LinkNode ? = head;
            var high: LinkNode ? = head;
            while (high != null 
                  && high.next != null 
                  && high.next?.next != null
                  && high.next != tail 
                  && head.next?.next != tail)
            {
                //visit to next node
                low = low?.next;
                //visit to second next node
                high = high.next?.next;
            }
            return low;
        }
    }
    // Merge two sorted list and return its result
    fun mergeList(l1: LinkNode ? , l2 : LinkNode ? ): LinkNode ?
    {
        
        var list1: LinkNode ? = l1;
        var list2: LinkNode ? = l2;
        if (list1 == null)
        {
            //When list1 is empty
            return list2;
        }
        else if (list2 == null)
        {
            return list1;
        }
        else
        {
            // Some auxiliary variables
            var result: LinkNode ? = null;
            var tail: LinkNode ? = null;
            var node: LinkNode?;
            // Combine list elements in sorted order
            // This process takes(m+n) time
            // Here m is size of list1
            // And n is size of list2
            while (list1 != null || list2 != null)
            {
                if (list1 != null && list2 != null)
                {
                    //When both list contain nodes
                    if (list1.element < list2.element)
                    {
                        //When first list element are smallest
                        node = list1;
                        list1 = list1.next;
                    }
                    else
                    {
                        //When second list element are smallest
                        node = list2;
                        list2 = list2.next;
                    }
                }
                else if (list1 != null)
                {
                    //When first list contain element
                    //Get sublist
                    node = list1;
                    //Set that list1 empty
                    list1 = null;
                }
                else
                {
                    //When second list contain element
                    //get sublist
                    node = list2;
                    list2 = null;
                }
                if (result == null)
                {
                    //When get first node of resultant list
                    result = node;
                    node?.next = null;
                    node?.prev = null;
                }
                else
                {
                    //Add node at end of resultant list
                    tail?.next = node;
                    node?.prev = tail;
                }
                tail = node;
            }
            return result;
        }
    }
    // Perform merge sort
    fun mergeSort(head: LinkNode ? , tail : LinkNode ? ): LinkNode ?
    {
        if (head == null || head == tail || head.next == null)
        {
            // When have zero or one node
            return head;
        }
        // Find the relative middle node
        var middle: LinkNode ? = this.middleNode(head, tail);
        // Get the right sublist
        var right: LinkNode ? = this.mergeSort(middle?.next, tail);
        // Separating sublist
        if (middle?.next != null)
        {
            middle.next?.prev = null;
        }
        middle?.next = null;
        //Get the left sublist
        var left: LinkNode ? = this.mergeSort(head, middle);
        
        // Sorted merge in two list
        return this.mergeList(left, right);
    }
    // Handles the request to perform merge sort operation
    fun sortList(dll: DoublyLL ): Unit
    {
        dll.front = this.mergeSort(dll.front, dll.rear);
        var node: LinkNode ? = dll.front;
        // First last node
        while (node?.next != null)
        {
            node = node.next;
        }
        // Set new rear node
        dll.rear = node;
    }
}
fun main(args: Array < String > ): Unit
{
    var dll: DoublyLL = DoublyLL();
    var task: Sorting = Sorting();
    dll.addNode(5);
    dll.addNode(3);
    dll.addNode(7);
    dll.addNode(1);
    dll.addNode(9);
    dll.addNode(6);
    dll.addNode(2);
    dll.addNode(8);
    dll.addNode(-2);
    dll.addNode(0);
    print("\n Before Sort \n");
    // 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
    dll.printData();
    task.sortList(dll);
    print("\n After Sort \n");
    //-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
    dll.printData();
}

Output

 Before Sort

 Linked List of from front to rear
 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
 Linked List of from rear to front
 0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL

 After Sort

 Linked List of from front to rear
 -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
 Linked List of from rear to front
 9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment