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

↓

Check if list has 0 or 1 node?

Yes→Return head (already sorted)

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

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

This code splits the list, sorts each half recursively, and merges them back sorted.

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 node	4 nodes	mid points to 2	4 -> 2 -> 1 -> 3 -> NULL
3	Split list at mid	Left: 4->2->NULL, Right: 1->3->NULL	mid->next = NULL	Left: 4 -> 2 -> NULL, Right: 1 -> 3 -> NULL
4	Recursively sort left half	2 nodes: 4->2->NULL	head points to 4	4 -> 2 -> NULL
5	Find middle of left half	2 nodes	mid points to 4	4 -> 2 -> NULL
6	Split left half	Left: 4->NULL, Right: 2->NULL	mid->next = NULL	Left: 4 -> NULL, Right: 2 -> NULL
7	Sort left-left half	1 node: 4->NULL	head points to 4	4 -> NULL
8	Sort left-right half	1 node: 2->NULL	head points to 2	2 -> NULL
9	Merge left halves	2 nodes	merge 4 and 2	2 -> 4 -> NULL
10	Recursively sort right half	2 nodes: 1->3->NULL	head points to 1	1 -> 3 -> NULL
11	Find middle of right half	2 nodes	mid points to 1	1 -> 3 -> NULL
12	Split right half	Left: 1->NULL, Right: 3->NULL	mid->next = NULL	Left: 1 -> NULL, Right: 3 -> NULL
13	Sort right-left half	1 node: 1->NULL	head points to 1	1 -> NULL
14	Sort right-right half	1 node: 3->NULL	head points to 3	3 -> NULL
15	Merge right halves	2 nodes	merge 1 and 3	1 -> 3 -> NULL
16	Merge sorted halves	4 nodes	merge 2->4 and 1->3	1 -> 2 -> 3 -> 4 -> NULL
17	Return sorted list	4 nodes	head points to 1	1 -> 2 -> 3 -> 4 -> NULL
18	End	Sorted list returned	No pointer changes	1 -> 2 -> 3 -> 4 -> NULL

💡 All nodes merged back in sorted order, recursion ends.

Variable Tracker

Variable	Start	After Step 3	After Step 9	After Step 15	After Step 16	Final
head	4->2->1->3->NULL	Left:4->2->NULL, Right:1->3->NULL	Left sorted:2->4->NULL	Right sorted:1->3->NULL	Merged:1->2->3->4->NULL	1->2->3->4->NULL
mid	points to 2	points to 4 (left half)	points to 4 (left half)	points to 1 (right half)	points to 1 (right half)	N/A
left	N/A	4->2->NULL	2->4->NULL	2->4->NULL	2->4->NULL	2->4->NULL
right	N/A	1->3->NULL	1->3->NULL	1->3->NULL	1->3->NULL	1->3->NULL

Key Moments - 3 Insights

Why do we split the list by setting mid->next = NULL?

Setting mid->next = NULL breaks the list into two separate halves so recursive calls sort each half independently, as shown in step 3 and step 6.

Why does the recursion stop when the list has 0 or 1 node?

A list with 0 or 1 node is already sorted, so the function returns immediately without further splitting, as seen in steps 7 and 8.

How does merging two sorted halves maintain order?

During merge (steps 9, 15, 16), nodes are compared one by one and linked in ascending order, ensuring the merged list is sorted.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after step 9?

A 2 -> 4 -> NULL

B 1 -> 3 -> NULL

C 4 -> 2 -> NULL

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

💡 Hint

Check the 'Visual State' column at step 9 in the execution table.

At which step does the list get fully merged and sorted?

A Step 9

B Step 16

C Step 15

D Step 3

💡 Hint

Look for the step where the full 4-node list is merged in the execution table.

If the original list had only one node, what would happen in the execution?

A The function would split the list anyway.

B The function would merge with an empty list.

C The function would return the node immediately without splitting.

D The function would cause an error.

💡 Hint

Refer to the base case condition in the code and steps 7 and 8.

Concept Snapshot

Merge Sort on Linked List:
- Base case: 0 or 1 node returns as sorted
- Find middle node to split list
- 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 sorted until we reach lists with one node, which are already sorted. Then, we merge the sorted halves step by step, comparing nodes to maintain order. Pointer changes like setting mid->next to NULL split the list physically. The final merged list is sorted. Key points include why we split the list, when recursion stops, and how merging maintains order.

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