Example: Linked List Merge Sort in C

// Linked List Merge Sort
#include <stdio.h>
#include <stdlib.h> // For malloc

// Define the structure for a linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the end of the list
void insertEnd(struct Node** head_ref, int data) {
    struct Node* newNode = createNode(data);
    if (*head_ref == NULL) {
        *head_ref = newNode;
        return;
    }
    struct Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}

// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

// Function to split the list into two halves.
// If the list has an odd number of nodes, the first list will have one more node.
void splitList(struct Node* source, struct Node** frontRef, struct Node** backRef) {
    struct Node* fast;
    struct Node* slow;
    slow = source;
    fast = source->next; // Start fast one step ahead

    // Advance 'fast' by two nodes, and 'slow' by one node
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    // 'slow' is now at the middle, so split it in two.
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL; // Terminate the first half
}

// Function to merge two sorted linked lists
struct Node* mergeSortedLists(struct Node* a, struct Node* b) {
    struct Node* result = NULL;

    // Base cases
    if (a == NULL)
        return b;
    if (b == NULL)
        return a;

    // Pick either 'a' or 'b', and recur
    if (a->data <= b->data) {
        result = a;
        result->next = mergeSortedLists(a->next, b);
    } else {
        result = b;
        result->next = mergeSortedLists(a, b->next);
    }
    return result;
}

// Function to sort a linked list using Merge Sort
void mergeSortLinkedList(struct Node** headRef) {
    struct Node* head = *headRef;
    struct Node* a;
    struct Node* b;

    // Base case : if head is NULL or has only one node
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    // Split head into 'a' and 'b' sublists
    splitList(head, &a, &b);

    // Recursively sort the sublists
    mergeSortLinkedList(&a);
    mergeSortLinkedList(&b);

    // Merge the two sorted sublists
    *headRef = mergeSortedLists(a, b);
}

int main() {
    // Step 1: Initialize an empty linked list
    struct Node* head = NULL;

    // Step 2: Insert elements into the list
    insertEnd(&head, 10);
    insertEnd(&head, 30);
    insertEnd(&head, 20);
    insertEnd(&head, 50);
    insertEnd(&head, 40);
    insertEnd(&head, 5); // Add an extra element for more robust testing

    // Step 3: Print the original list
    printf("Original list: ");
    printList(head);

    // Step 4: Sort the linked list using Merge Sort
    mergeSortLinkedList(&head);

    // Step 5: Print the sorted list
    printf("Sorted list (Merge Sort): ");
    printList(head);

    // Step 6: Free allocated memory
    struct Node* current = head;
    struct Node* next_node;
    while (current != NULL) {
        next_node = current->next;
        free(current);
        current = next_node;
    }
    head = NULL;

    return 0;
}