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: Like sorting a deck of cards by splitting it into smaller piles, sorting each pile, then carefully merging them back into one sorted deck.

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

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

Why: Splitting helps break the problem into smaller parts

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

4 -> null and 2 -> null after splitting, then merge sorted halves

Why: Sort smaller parts before merging

Step 3: Merge sorted left half: 2 -> 4 -> null

2 -> 4 -> null

Why: Combine sorted nodes in order

Step 4: Recursively sort right half (1 -> 3 -> null)

1 -> null and 3 -> null after splitting, then merge sorted halves

Why: Sort smaller parts before merging

Step 5: Merge sorted right half: 1 -> 3 -> null

1 -> 3 -> null

Why: Combine sorted nodes in order

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

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

Why: Final merge produces fully sorted list

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

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

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

// Merge two sorted linked lists
Node* merge(Node* left, Node* right) {
    if (!left) return right;
    if (!right) return left;
    if (left->data <= right->data) {
        left->next = merge(left->next, right); // merge rest
        return left;
    } else {
        right->next = merge(left, right->next); // merge rest
        return right;
    }
}

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

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

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

    head = mergeSort(head);

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

    return 0;
}

Node* slow = head; Node* fast = head->next; while (fast && fast->next) { slow = slow->next; // advance slow by one fast = fast->next->next; // advance fast by two }

Find middle node by moving slow one step and fast two steps

mid->next = nullptr; // split list

Break list into two halves at middle

Node* left = mergeSort(head); // sort left half Node* right = mergeSort(rightHead); // sort right half

Recursively sort each half

if (left->data <= right->data) { left->next = merge(left->next, right); // merge rest return left; } else { right->next = merge(left, right->next); // merge rest return right; }

Merge two sorted lists by choosing smaller head 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 merged (n operations per merge)

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

vs Alternative: Better than bubble or insertion sort on linked lists which are O(n^2), merge sort efficiently handles linked lists without random access

Edge Cases

empty list

Returns null immediately without error

DSA C++

if (!head || !head->next) return head; // base case

single element list

Returns the single node as sorted list

DSA C++

if (!head || !head->next) return head; // base case

list with duplicate values

Duplicates are kept and sorted correctly

DSA C++

if (left->data <= right->data) { ... } else { ... } // merge preserves duplicates

When to Use This Pattern

When you need to sort a linked list efficiently without extra space, use merge sort because it splits and merges lists naturally using pointers.

Common Mistakes

Mistake: Not breaking the list into two halves properly causing infinite recursion
Fix: Set mid->next = nullptr to split the list into two separate lists

Mistake: Merging lists incorrectly by not updating next pointers properly
Fix: Recursively merge by choosing smaller node and linking its next to merged remainder

Summary

Sorts a linked list by recursively splitting and merging sorted halves.

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

The key is to find the middle, split the list, sort halves, then merge back in order.

Practice

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

easy

A. It only works for arrays, not linked lists.

B. It sorts the list in O(n^2) time but uses less memory.

C. It efficiently sorts the list in O(n log n) time without extra space for arrays.

D. It requires the list to be converted to an array first.

Solution

1. Step 1: Understand merge sort time complexity on linked lists

   Merge sort divides the list and merges sorted halves, achieving O(n log n) time.

2. Step 2: Compare space usage with other sorts

   Unlike quicksort or heapsort on arrays, merge sort on linked lists does not need extra arrays, so it uses less extra space.

3. Final Answer:

   It efficiently sorts the list in O(n log n) time without extra space for arrays. -> Option C

4. Quick Check:

   Merge sort = O(n log n) + low extra space [OK]

Hint: Merge sort is best for linked lists due to O(n log n) and no array needed [OK]

Common Mistakes:

• Thinking merge sort uses extra arrays for linked lists
• Confusing merge sort with bubble sort time complexity
• Assuming linked lists must be converted to arrays first

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

easy

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

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

C. Split by dividing the node values by 2.

D. Use recursion without splitting the list.

Solution

1. Step 1: Identify the standard splitting technique

   Using two pointers, slow and fast, where fast moves twice as fast, slow ends at middle.

2. Step 2: Explain why other options are incorrect

   Counting nodes is less efficient; dividing values is meaningless; recursion needs splitting first.

3. Final Answer:

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

4. Quick Check:

   Two-pointer split = Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks middle. [OK]

Hint: Use slow-fast pointer method to find middle in one pass [OK]

Common Mistakes:

• Trying to split by counting nodes first
• Splitting based on node values instead of positions
• Not splitting before recursive calls

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

medium

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

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

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

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

Solution

1. Step 1: Break list into halves and sort recursively

   Split into (4 -> 2) and (1 -> 3), sort each: (2 -> 4), (1 -> 3).

2. Step 2: Merge sorted halves

   Merge (2 -> 4) and (1 -> 3) to get (1 -> 2 -> 3 -> 4).

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> null -> Option A

4. Quick Check:

   Sorted ascending = 1 -> 2 -> 3 -> 4 -> null [OK]

Hint: Merge sort always returns ascending sorted list [OK]

Common Mistakes:

• Confusing merge order and producing descending list
• Not fully sorting both halves before merging
• Merging without comparing node values

4. In the following merge sort code for linked list, what is the bug?

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 = nullptr;
  Node* left = mergeSort(head);
  Node* right = mergeSort(mid);
  return merge(left, right);
}

medium

A. The base case should check only if head is nullptr.

B. Slow pointer should move twice as fast as fast pointer.

C. The merge function is called with wrong arguments.

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

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer starting at head causes incorrect middle for even length lists.

2. Step 2: Correct initialization for proper middle detection

   Fast should start at head->next to ensure slow points to middle correctly.

3. Final Answer:

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

4. Quick Check:

   Fast pointer start = head->next [OK]

Hint: Start fast pointer at head->next to find middle correctly [OK]

Common Mistakes:

• Starting fast pointer at head causing wrong split
• Confusing slow and fast pointer speeds
• Ignoring base case for single node

5. You have a linked list with nodes containing duplicate values: 5 -> 3 -> 8 -> 3 -> 5 -> null. After applying merge sort, what will be the correct sorted linked list?

hard

A. 3 -> 3 -> 5 -> 5 -> 8 -> null

B. 5 -> 3 -> 8 -> 3 -> 5 -> null

C. 8 -> 5 -> 5 -> 3 -> 3 -> null

D. 3 -> 5 -> 8 -> 3 -> 5 -> null

Solution

1. Step 1: Understand merge sort handles duplicates by comparing values

   During merge, nodes with equal values are placed in order preserving duplicates.

2. Step 2: Sort the list step-by-step

   Sorted order is ascending: 3, 3, 5, 5, 8.

3. Final Answer:

   3 -> 3 -> 5 -> 5 -> 8 -> null -> Option A

4. Quick Check:

   Duplicates preserved and sorted ascending [OK]

Hint: Merge sort keeps duplicates and sorts ascending [OK]

Common Mistakes:

• Assuming duplicates are removed
• Sorting in descending order by mistake
• Not merging duplicates correctly