Example: Linked List Merge Sort in C++

// Linked List Merge Sort
#include <iostream>
#include <cstddef> // For NULL

using namespace std;

// Node structure for the linked list
struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(NULL) {}
};

// Function to merge two sorted linked lists
Node* mergeTwoSortedLists(Node* list1, Node* list2) {
    // Base cases
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    Node* result = NULL;

    // Pick either list1 or list2, and recurse
    if (list1->data <= list2->data) {
        result = list1;
        result->next = mergeTwoSortedLists(list1->next, list2);
    } else {
        result = list2;
        result->next = mergeTwoSortedLists(list1, list2->next);
    }
    return result;
}

// Function to find the middle of a linked list
Node* getMiddle(Node* head) {
    if (head == NULL) return head;

    Node* slow = head;
    Node* fast = head->next; // Start fast one ahead

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Function to sort a linked list using Merge Sort
Node* mergeSort(Node* head) {
    // Base case: if head is NULL or has only one node
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // Step 1: Find the middle of the list to divide it into two halves
    Node* middle = getMiddle(head);
    Node* nextOfMiddle = middle->next; // Store the head of the second half

    // Step 2: Break the link to split the list into two halves
    middle->next = NULL;

    // Step 3: Recursively sort the two halves
    Node* left = mergeSort(head);
    Node* right = mergeSort(nextOfMiddle);

    // Step 4: Merge the sorted halves
    Node* sortedList = mergeTwoSortedLists(left, right);

    return sortedList;
}

// Function to print the linked list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Step 1: Create an unsorted linked list
    Node* head = new Node(5);
    head->next = new Node(2);
    head->next->next = new Node(8);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(4);
    head->next->next->next->next->next = new Node(9); // Added one more for odd length

    cout << "Original list: ";
    printList(head);

    // Step 2: Sort the linked list using Merge Sort
    head = mergeSort(head);

    cout << "Sorted list (Merge Sort): ";
    printList(head);

    // Step 3: Clean up memory
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}