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.

Practice

1. What is the main advantage of using merge sort to sort a linked list compared to quicksort?

easy

A. Merge sort does not require random access, which suits linked lists well.

B. Quicksort uses less memory than merge sort for linked lists.

C. Merge sort is faster than quicksort on arrays.

D. Quicksort is stable while merge sort is not.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, unlike arrays.

2. Step 2: Compare sorting algorithms

   Merge sort works well with sequential access, while quicksort relies on random access for efficiency.

3. Final Answer:

   Merge sort does not require random access, which suits linked lists well. -> Option A

4. Quick Check:

   Linked list + merge sort = no random access needed [OK]

Hint: Merge sort fits linked lists due to sequential access [OK]

Common Mistakes:

• Thinking quicksort is always better
• Assuming merge sort needs random access
• Confusing stability of sorting algorithms

2. Which of the following is the correct way to split a linked list into two halves for merge sort in C?

easy

A. Split by dividing the node values by 2.

B. Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks mid.

C. Use a single pointer to count nodes and split at half count.

D. Use recursion without splitting the list.

Solution

1. Step 1: Identify splitting technique

   The fast and slow pointer method finds the middle node efficiently.

2. Step 2: Understand pointer movement

   Slow pointer moves one node at a time, fast pointer moves two nodes; when fast reaches end, slow is at mid.

3. Final Answer:

   Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks mid. -> Option B

4. Quick Check:

   Fast/slow pointers split linked list [OK]

Hint: Use fast/slow pointers to find middle node [OK]

Common Mistakes:

• Trying to split by node values
• Using only one pointer to split
• Not stopping fast pointer correctly

3. Given the linked list: 4 -> 2 -> 1 -> 3 -> NULL, what is the sorted list after applying merge sort?

medium

A. 4 -> 3 -> 2 -> 1 -> NULL

B. 1 -> 3 -> 2 -> 4 -> NULL

C. 2 -> 1 -> 3 -> 4 -> NULL

D. 1 -> 2 -> 3 -> 4 -> NULL

Solution

1. Step 1: Break list into halves recursively

   Split into (4 -> 2) and (1 -> 3), then further split until single nodes.

2. Step 2: Merge sorted halves

   Merge nodes in order: 1, 2, 3, 4 to get sorted list.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> NULL -> Option D

4. Quick Check:

   Sorted ascending order = 1,2,3,4 [OK]

Hint: Merge sort outputs ascending sorted list [OK]

Common Mistakes:

• Confusing merge order
• Not splitting correctly
• Assuming original order remains

4. In the following C code snippet for merge sort on linked list, what is the error?

Node* mergeSort(Node* head) {
  if (!head || !head->next) return head;
  Node* slow = head;
  Node* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  Node* mid = slow->next;
  slow->next = NULL;
  Node* left = mergeSort(head);
  Node* right = mergeSort(mid);
  return merge(left, right);
}

medium

A. The base case should check only for head->next, not head.

B. Slow pointer should move two steps each iteration.

C. Fast pointer should start at head->next, not head.

D. The function should not split the list.

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer should start at head->next to correctly find middle for even nodes.

2. Step 2: Understand pointer movement impact

   Starting fast at head skips the first node, causing incorrect mid calculation.

3. Final Answer:

   Fast pointer should start at head->next, not head. -> Option C

4. Quick Check:

   Fast pointer start affects mid node [OK]

Hint: Start fast pointer at head->next for correct mid [OK]

Common Mistakes:

• Starting fast at head
• Moving slow pointer incorrectly
• Ignoring base case conditions

5. You have a linked list with duplicate values: 5 -> 3 -> 8 -> 5 -> 2 -> NULL. After applying merge sort, which of the following is the correct sorted list?

hard

A. 2 -> 3 -> 5 -> 5 -> 8 -> NULL

B. 5 -> 3 -> 8 -> 5 -> 2 -> NULL

C. 2 -> 3 -> 8 -> 5 -> 5 -> NULL

D. 3 -> 2 -> 5 -> 5 -> 8 -> NULL

Solution

1. Step 1: Understand merge sort stability

   Merge sort preserves order of equal elements, so duplicates stay in relative order.

2. Step 2: Sort values ascending

   Sorted order is 2, 3, 5, 5, 8 with duplicates adjacent.

3. Final Answer:

   2 -> 3 -> 5 -> 5 -> 8 -> NULL -> Option A

4. Quick Check:

   Sorted with duplicates preserved = 2,3,5,5,8 [OK]

Hint: Merge sort keeps duplicates in order [OK]

Common Mistakes:

• Assuming duplicates get removed
• Sorting duplicates incorrectly
• Mixing order of duplicates