Solution: Sorting Algorithms

#include <iostream>
#include <functional>
using namespace std;
template<typename T>
class Node {
public:
    T data;
    Node<T>* prev;
    Node<T>* next;
    Node(const T& data) : data(data), prev(nullptr), next(nullptr) {}
};
template<typename T>
class MergeSortDLL {
private:
    Node<T>* head;
    function<bool(const T&, const T&)> compare;
public:
    MergeSortDLL(const function<bool(const T&, const T&)>& compare)
        : head(nullptr), compare(compare) {}
    void add(const T& data) {
        Node<T>* newNode = new Node<T>(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node<T>* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
            newNode->prev = current;
        }
    }
    void mergeSort() {
        head = mergeSort(head);
    }
    Node<T>* mergeSort(Node<T>* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        Node<T>* middle = getMiddle(head);
        Node<T>* nextOfMiddle = middle->next;
        middle->next = nullptr;
        Node<T>* left = mergeSort(head);
        Node<T>* right = mergeSort(nextOfMiddle);
        return merge(left, right);
    }
    Node<T>* merge(Node<T>* left, Node<T>* right) {
        Node<T>* result = nullptr;
        if (left == nullptr) {
            return right;
        }
        if (right == nullptr) {
            return left;
        }
        if (compare(left->data, right->data)) {
            result = left;
            result->next = merge(left->next, right);
            result->next->prev = result;
        } else {
            result = right;
            result->next = merge(left, right->next);
            result->next->prev = result;
        }
        return result;
    }
    Node<T>* getMiddle(Node<T>* head) {
        if (head == nullptr) {
            return nullptr;
        }
        Node<T>* slow = head;
        Node<T>* fast = head->next;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    void printList() {
        Node<T>* current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};
int main() {
    MergeSortDLL<int> mergeSortDLL([](const int& a, const int& b) {
        return a <= b;
    });
    mergeSortDLL.add(5);
    mergeSortDLL.add(2);
    mergeSortDLL.add(9);
    mergeSortDLL.add(1);
    mergeSortDLL.add(3);
    mergeSortDLL.add(6);
    cout << "Original List: ";
    mergeSortDLL.printList();
    mergeSortDLL.mergeSort();
    cout << "Sorted List: ";
    mergeSortDLL.printList();
    return 0;
}