Sort a Linked List Using Merge Sort in DSA C

Mental Model

Split the list into halves, sort each half, then merge them back in order. Repeat until the whole list is sorted.

Analogy: Imagine sorting a deck of cards by splitting it into smaller piles, sorting each pile, then carefully merging the piles back together in order.

head -> 4 -> 2 -> 1 -> 3 -> null

Dry Run Walkthrough

Input: list: 4 -> 2 -> 1 -> 3 -> null

Goal: Sort the linked list so nodes are in ascending order

Step 1: Find middle to split list into two halves

4 -> 2 -> null and 1 -> 3 -> null

Why: Splitting helps break down the problem into smaller parts

Step 2: Recursively sort left half 4 -> 2 -> null

2 -> 4 -> null

Why: Sorting smaller parts first makes merging easier

Step 3: Recursively sort right half 1 -> 3 -> null

1 -> 3 -> null

Why: Right half is already sorted or smaller to sort

Step 4: Merge sorted halves 2 -> 4 and 1 -> 3

1 -> 2 -> 3 -> 4 -> null

Why: Merging combines sorted lists into one sorted list

Result:

1 -> 2 -> 3 -> 4 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

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

// Function to create a new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

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

// Function to find middle of linked list
Node* getMiddle(Node* head) {
    if (head == NULL) return head;
    Node* slow = head;
    Node* fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next; // advance slow by one
        fast = fast->next->next; // advance fast by two
    }
    return slow; // slow is middle
}

// Function to merge two sorted lists
Node* sortedMerge(Node* a, Node* b) {
    if (a == NULL) return b;
    if (b == NULL) return a;
    Node* result = NULL;
    if (a->data <= b->data) {
        result = a; // pick a
        result->next = sortedMerge(a->next, b); // merge rest
    } else {
        result = b; // pick b
        result->next = sortedMerge(a, b->next); // merge rest
    }
    return result;
}

// Merge sort function for linked list
Node* mergeSort(Node* head) {
    if (head == NULL || head->next == NULL) return head; // base case
    Node* middle = getMiddle(head); // find middle
    Node* nextToMiddle = middle->next;
    middle->next = NULL; // split list
    Node* left = mergeSort(head); // sort left half
    Node* right = mergeSort(nextToMiddle); // sort right half
    Node* sortedList = sortedMerge(left, right); // merge sorted halves
    return sortedList;
}

int main() {
    // Create list 4 -> 2 -> 1 -> 3 -> null
    Node* head = newNode(4);
    head->next = newNode(2);
    head->next->next = newNode(1);
    head->next->next->next = newNode(3);

    printf("Original list:\n");
    printList(head);

    head = mergeSort(head);

    printf("Sorted list:\n");
    printList(head);

    return 0;
}

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

advance slow and fast pointers to find middle node

middle->next = NULL;

split list into two halves by breaking link at middle

Node* left = mergeSort(head);

recursively sort left half

Node* right = mergeSort(nextToMiddle);

recursively sort right half

result = (a->data <= b->data) ? a : b; result->next = sortedMerge(...);

merge two sorted lists by picking smaller node each time

Output

Original list:

4 -> 2 -> 1 -> 3 -> null

Sorted list:

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merging takes O(n) each time

Space: O(log n) due to recursion stack depth from splitting the list

vs Alternative: Compared to bubble sort O(n^2), merge sort is much faster for linked lists because it avoids repeated scanning and swapping

Edge Cases

empty list

returns NULL immediately without error

DSA C

if (head == NULL || head->next == NULL) return head;

single element list

returns the single node as sorted list

DSA C

if (head == NULL || head->next == NULL) return head;

list with duplicate values

duplicates are kept and sorted correctly

DSA C

if (a->data <= b->data) { result = a; ... } else { result = b; ... }

When to Use This Pattern

When asked to sort a linked list efficiently, reach for merge sort because it works well with linked lists without random access.

Common Mistakes

Mistake: Not breaking the list at the middle, causing infinite recursion
Fix: Set middle->next = NULL to split the list before recursive calls

Mistake: Using fast pointer starting at head instead of head->next, causing wrong middle
Fix: Start fast pointer at head->next to find middle correctly

Mistake: Merging lists incorrectly by not updating next pointers properly
Fix: Use recursive merge that sets result->next to merged remainder

Summary

Sorts a linked list by splitting it into halves, sorting each half, and merging them back.

Use when you need an efficient O(n log n) sort for linked lists without extra space for arrays.

The key insight is to break the list into smaller parts and merge sorted parts carefully.