Signup/Sign In

Using Merge Sort to Sort a Doubly Linked List

Posted in Programming   LAST UPDATED: SEPTEMBER 3, 2021

    We have already covered Merge Sort for single linked list in our previous post. The merge sort algorithm on doubly linked list works in a similar way, which is by splitting the list into two halves, and then sorting each sublist recursively and finally merging both the sorted list together to get single sorted list.

    Just like a normal merge sort algorithm works by breaking a array into two parts, then breaking the two parts further into smaller data set until a data set has only a single data element and we know that a single data element is by default sorted, then we start merging the data elements, eventually getting the sorted list.

    The important change here in case of doubly linked list is that we will have to modify the previous pointers of the node also while merging any two sublists.


    Implementation in C/C++:

    In the code below, we have a structure node which will store data and next and previous pointers. Whenever we implement a Linked List we have to create a node because a linked list is nothing but a list of nodes.

    #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 poitner\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;
    }

    In the code above we have a function split() used for splitting the doubly linked list into two sublist and we are calling it from inside the mergeSort() function and then we are again calling the function mergeSort() on the two sublist, hence this becomes a recursive call.

    And at the end we call merge() function to merge the two sublist into one list.


    Time Complexity of the Algorithm

    The time complexity of this algorithm is same as the time complexity for the merge sort for arrays; i.e. O(nlogn)

    If you think the above program can be improved then please do share your code in the comment section below.

    You may also like:

    About the author:
    I am currently pursuing Bachelor of Technology (B.Tech) in the stream of Computer Science and Engineering from ABES Engineering College, Ghaziabad. I am currently in the final year of Bachelor Degree. My hobbies are playing and watching cricket.
    Tags:Data StructuresAlgorithmMerge SortDoubly Linked List
    IF YOU LIKE IT, THEN SHARE IT
     

    RELATED POSTS