Merge Sort for Doubly Linked List - GeeksforGeeks

Merge Sort for Doubly Linked List - GeeksforGeeks
Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort.

// 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;

}

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);

}

Read full article from Merge Sort for Doubly Linked List - GeeksforGeeks