MergeSort on Doubly Linked List

[mpark4656]

I'm trying to implement mergesort on doubly linked list that guarantees the worst case of O(n log n) without destroying any node. The head pointer is updated while sorting. However, I can't quite figure out how to update the tail node while sorting. For now, after sort is complete, I simply start from the head and iterate to the end node and assign the tail to it. Can anyone provide suggestions on how to optimize the mergesort?

#include <iostream>
#include <algorithm>
#include <initializer_list>

class LinkedList
{
private:
    struct Node
    {
        int data = 0;
        Node* next = nullptr;
        Node* prev = nullptr;

        Node( int data ): next{ nullptr } , prev{ nullptr } , data{ data }
        { }
    };

public:
    // Default Constructor
    LinkedList() {}

    // Destructor
    ~LinkedList()
    {
        while( head != nullptr ) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    /**
     *  Public function that sorts the elements in this list by invoking
     *      the private function that accepts head pointer.
     */
    void sort()
    {
        sort( head );

        // After the merge sort, tail pointer will be pointing to incorrect node
        // Update the tail (*** Need a better way to update tail ***)
        Node* findTail = head;
        while( findTail != nullptr ) {
            if( findTail->next == nullptr ) {
                tail = findTail;
            }

            findTail = findTail->next;
        }
    }

    void push_back( int x )
    {
        if( tail == nullptr ) {
            tail = new Node{ x };
            head = tail;
            theSize++;
        }
        else {
            Node* temp = tail;
            tail = new Node{ x };
            temp->next = tail;
            tail->prev = temp;
            theSize++;
        }
    }

    void display() const
    {
        Node* current = head;

        while( current != nullptr ) {
            std::cout << current->data << std::endl;
            current = current->next;
        }
    }

private:
    Node* head = nullptr;
    Node* tail = nullptr;
    int theSize = 0;

    /**
     *  Perform merge sort on the this list.
     *  @param theHead Node* Reference to the head
     */
    void sort( Node* &theHead )
    {
        Node* a = nullptr;
        Node* b = nullptr;

        // Base case
        if( theHead == nullptr || theHead->next == nullptr ) {
            return;
        }

        // Split the list in half
        // For odd number of nodes, the extra node will be in the first half.
        frontBackSplit( theHead , a , b );

        // Recursively break the list down until the sublist contains 1 element (Sorted)
        sort( a );
        sort( b );

        // Merge the two sorted lists
        theHead = sortedMerge( a , b );
    }

    /**
     *  Take 2 Node Pointers, each pointing at the head of sorted sublist,
     *      merge them, and return the Node pointer to the head node of the merged list.
     *  @param a Node* Pointer to the head of the first sorted list
     *  @param b Node* Pointer to the head of the second sorted list
     *  @return Node* head of the merged list (nullptr if both given nodes are empty)
     */
    Node* sortedMerge( Node* a , Node* b )
    {
        Node* headOfMerged;

        // If one of the node is nullptr, return the other node
        // No merging occurs this this case
        if( a == nullptr ) {
            return b;
        }
        else if( b == nullptr ) {
            return a;
        }

        // First element in list, a, is less than the first element in b
        if( a->data <= b->data ) {
            headOfMerged = a;

            while( b != nullptr ) {
                if( a->data <= b->data ) {
                    if( a->next == nullptr ) {
                        a->next = b;
                        b->prev = a;
                        break;
                    }
                    a = a->next;
                }
                else {
                    Node* toAdd = b;
                    b = b->next;
                    toAdd->prev = a->prev;
                    a->prev->next = toAdd;
                    toAdd->next = a;
                    a->prev = toAdd;
                }
            }
        }
        // First element in list, b, is less than the first element in a
        else {
            headOfMerged = b;

            while( a != nullptr ) {
                if( b->data <= a->data ) {
                    if( b->next == nullptr ) {
                        b->next = a;
                        a->prev = b;
                        break;
                    }
                    b = b->next;
                }
                else {
                    Node* toAdd = a;
                    a = a->next;
                    toAdd->prev = b->prev;
                    b->prev->next = toAdd;
                    toAdd->next = b;
                    b->prev = toAdd;
                }
            }
        }

        return headOfMerged;
    }

    /**
     *  Utility function for merge sort
     *  @param frontRef Node* reference pointer that will point to the head of first sorted half
     *  @param backRef Node* reference pointer that will point to the head of second sorted half
     */
    void frontBackSplit( Node* theHead , Node* &frontRef , Node* &backRef )
    {
        Node* fast;
        Node* slow;

        // If the list is empty, both front and back points to null
        // If there is only one element, front points to it and back points
        //  to null.
        if( theHead == nullptr || theHead->next == nullptr ) {
            frontRef = theHead;
            backRef = nullptr;
        }
        else {
            slow = theHead;
            fast = theHead->next;

            // Fast advances 2 nodes while slow advances 1 node
            while( fast != nullptr ) {
                fast = fast->next;

                if( fast != nullptr ) {
                    slow = slow->next;
                    fast = fast->next;
                }
            }

            // slow should be pointing right before midpoint. Split at this point
            frontRef = theHead;
            backRef = slow->next;

            // Update the prev and next pointers
            backRef->prev = nullptr;
            slow->next = nullptr;
        }
    }
};

// Test Driver to test operations of LinkedList
int main()
{
    int n;
    std::cin >> n;
    LinkedList list1;

    for( int i = 0 ; i < n ; i++ ) {
        int input;
        std::cin >> input;
        list1.push_back( input );
    }

    list1.sort();

    list1.display();
}