Sort a Linked List Using Merge Sort in DSA C++ - Execution Trace

Concept Flow - Sort a Linked List Using Merge Sort

Start with head of list

↓

Base case: list empty or one node?

Yes→Return head

No↓

Split list into two halves

↓

Recursively sort left half

↓

Merge two sorted halves

↓

Return merged sorted list

The list is split into halves recursively until single nodes remain, then merged back in sorted order.

Execution Sample

DSA C++

struct Node {
  int val;
  Node* next;
};

Node* mergeSort(Node* head) {
  if (!head || !head->next) return head;
  // split, sort, merge
}

This code sorts a linked list by splitting it recursively and merging sorted halves.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with full list	4 nodes: 4->2->1->3->null	head points to 4	4 -> 2 -> 1 -> 3 -> null
2	Find middle to split	4 nodes: 4->2->1->3->null	slow at 2, fast at 3	Split after 2: Left: 4->2->null, Right: 1->3->null
3	Recursively sort left half	2 nodes: 4->2->null	head points to 4	4 -> 2 -> null
4	Split left half	2 nodes: 4->2->null	slow at 4, fast at 2	Split after 4: Left: 4->null, Right: 2->null
5	Sort left sublist (single node)	1 node: 4->null	head points to 4	4 -> null
6	Sort right sublist (single node)	1 node: 2->null	head points to 2	2 -> null
7	Merge sorted left and right sublists	2 nodes: 4->2->null	merged list head points to 2	2 -> 4 -> null
8	Recursively sort right half	2 nodes: 1->3->null	head points to 1	1 -> 3 -> null
9	Split right half	2 nodes: 1->3->null	slow at 1, fast at 3	Split after 1: Left: 1->null, Right: 3->null
10	Sort left sublist (single node)	1 node: 1->null	head points to 1	1 -> null
11	Sort right sublist (single node)	1 node: 3->null	head points to 3	3 -> null
12	Merge sorted left and right sublists	2 nodes: 1->3->null	merged list head points to 1	1 -> 3 -> null
13	Merge two sorted halves	4 nodes: 2->4->null and 1->3->null	merged list head points to 1	1 -> 2 -> 3 -> 4 -> null
14	Return fully sorted list	4 nodes: 1->2->3->4->null	head points to 1	1 -> 2 -> 3 -> 4 -> null

💡 Recursion ends when sublist has zero or one node (base case).

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 9	After Step 12	After Step 13	Final
head	4->2->1->3->null	4->2->null (left half)	4->null (left-left half)	2->4->null (sorted left half)	1->3->null (right half)	1->3->null (sorted right half)	1->2->3->4->null (merged full)	1->2->3->4->null
slow	4	2	4	4	1	1	1	1
fast	4	3	2	2	3	3	3	3
merged_head	null	null	null	2	null	1	1	1

Key Moments - 3 Insights

Why do we split the list at the middle node?

Splitting at the middle (Step 2 and Step 9) ensures the list is divided into two roughly equal halves, which is essential for merge sort's divide-and-conquer approach.

Why does the recursion stop when the list has one or zero nodes?

At Step 5 and Step 6, the base case returns the list as is because a single node or empty list is already sorted, preventing infinite recursion.

How do we merge two sorted lists back together?

At Step 7, Step 12, and Step 13, two sorted lists are merged by comparing their nodes one by one and linking the smaller node first, building a sorted combined list.

Visual Quiz - 3 Questions

Look at the execution table at Step 7, what is the head value of the merged left half?

A 2

B 4

C 1

D 3

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at Step 7 in the execution table.

At which step does the recursion first split the list into single nodes?

A Step 2

B Step 9

C Step 4

D Step 12

💡 Hint

Look for the first split that results in single-node lists in the execution table.

If the original list had 6 nodes instead of 4, how would the splitting steps change?

A Fewer splitting steps would appear

B More splitting steps would appear before merging

C No splitting would occur

D Merging would happen before splitting

💡 Hint

Consider how merge sort divides lists recursively as shown in the concept flow and execution table.

Concept Snapshot

Merge Sort on Linked List:
- Base case: empty or single node list is sorted
- Find middle using slow/fast pointers
- Recursively sort left and right halves
- Merge two sorted halves by comparing nodes
- Result is a fully sorted linked list

Full Transcript

This visualization shows how merge sort works on a linked list. We start with the full list and find the middle node to split it into two halves. Each half is recursively split until we reach lists with one or zero nodes, which are already sorted. Then, we merge these small sorted lists back together by comparing their nodes one by one, building larger sorted lists. This process continues until the entire list is merged and sorted. The key steps include finding the middle with slow and fast pointers, stopping recursion at single nodes, and merging sorted lists carefully. The final output is a sorted linked list.

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