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

Concept Flow - Sort a Linked List Using Merge Sort

Start with head node

↓

Base case: 0 or 1 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#

Node MergeSort(Node head) {
  if (head == null || head.next == null) return head;
  Node mid = GetMiddle(head);
  Node right = MergeSort(mid.next);
  mid.next = null;
  Node left = MergeSort(head);
  return Merge(left, right);
}

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

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: 4->2->1->3->null	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	4 -> 2 -> null and 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: 4->2->null	mid points to 4	4 -> 2 -> null
6	Split left half	Left: 4->null, Right: 2->null	mid.next = null	4 -> null and 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	4.next = 2 or 2.next = 4	2 -> 4 -> null (sorted)
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: 1->3->null	mid points to 1	1 -> 3 -> null
12	Split right half	Left: 1->null, Right: 3->null	mid.next = null	1 -> null and 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	1.next = 3 or 3.next = 1	1 -> 3 -> null (sorted)
16	Merge sorted left and right halves	4 nodes	4.next = 1 or 2.next = 1	1 -> 2 -> 3 -> 4 -> null (fully sorted)
17	Return sorted list	4 nodes	head points to 1	1 -> 2 -> 3 -> 4 -> null

💡 All nodes merged in sorted order, recursion ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 9	After Step 15	Final
head	4->2->1->3->null	4->2->1->3->null	4->2->null	2->4->null	2->4->null	1->2->3->4->null
mid	null	2	2	4	1	1
left	null	null	4->2->null	2->4->null	2->4->null	2->4->null
right	null	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.

How does the merge step keep the list sorted?

During merge (Step 9, 15, 16), nodes from two sorted halves are compared and linked in ascending order, ensuring the merged list remains sorted.

Why is the base case checking if head is null or head.next is null?

If the list has zero or one node (Step 7, 8, 13, 14), it is already sorted, so recursion stops and returns the node as is.

Visual Quiz - 3 Questions

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

A 4 -> 2 -> null

B 2 -> 4 -> null

C 1 -> 3 -> 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 split into two halves for the first time?

A Step 3

B Step 6

C Step 2

D Step 10

💡 Hint

Look for the first 'Split list at mid' operation in the execution_table.

If the list had only one node, which step would the function return immediately?

A Step 4

B Step 1

C Step 7

D Step 16

💡 Hint

Refer to the base case explanation in key_moments and Step 7 in execution_table.

Concept Snapshot

Merge Sort on Linked List:
- Base case: 0 or 1 node returns as is
- 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

Merge sort on a linked list works by splitting the list into two halves recursively until each sublist has one or zero nodes, which are inherently sorted. Then, it merges these sorted sublists back together in order. The key steps are finding the middle node to split the list, breaking the list into two parts by setting mid.next to null, recursively sorting each half, and merging the sorted halves by comparing node values. The base case stops recursion when the list is empty or has one node. The merge step carefully links nodes in ascending order to maintain sorting. This process continues until the entire list is sorted and returned.

Practice

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

easy

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

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

C. It requires the list to be converted into an array first.

D. It only works for linked lists with integer values.

Solution

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

   Merge sort divides the list into halves recursively and merges them, 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 require extra array space, making it memory efficient.

3. Final Answer:

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

4. Quick Check:

   Merge sort = O(n log n) + memory efficient [OK]

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

Common Mistakes:

• Thinking merge sort uses extra array space for linked lists
• Confusing merge sort with bubble sort time complexity
• Assuming merge sort only works on arrays
• Believing merge sort requires integer-only lists

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

easy

A. Convert the list to an array and split the array.

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

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

D. Split the list by removing the last node repeatedly.

Solution

1. Step 1: Identify the standard technique to find middle in linked list

   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 requires extra traversal; converting to array is inefficient; removing last node is not splitting in half.

3. Final Answer:

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

4. Quick Check:

   Two-pointer technique = correct split [OK]

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

Common Mistakes:

• Trying to split by counting nodes first
• Converting linked list to array unnecessarily
• Removing nodes instead of splitting
• Using only one pointer to find middle

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 down the list and sort halves recursively

   Split into (4 -> 2) and (1 -> 3). Sort each half: (2 -> 4) and (1 -> 3).

2. Step 2: Merge the two sorted halves

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge sorted halves step-by-step to get final sorted list [OK]

Common Mistakes:

• Not sorting halves before merging
• Merging without sorting causing wrong order
• Confusing node values during merge
• Forgetting to set last node's next to null

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

public ListNode MergeSort(ListNode head) {
  if (head == null || head.next == null) return head;
  ListNode mid = GetMiddle(head);
  ListNode left = MergeSort(head);
  ListNode right = MergeSort(mid);
  return Merge(left, right);
}

medium

A. The base case is incorrect; it should check for head.next.next.

B. The middle node is not disconnected from the left half, causing infinite recursion.

C. The Merge function is called before sorting the halves.

D. The GetMiddle function returns the last node instead of the middle.

Solution

1. Step 1: Identify the role of splitting the list

   After finding middle, the list must be split by setting middle's previous node next to null to separate halves.

2. Step 2: Explain the bug effect

   Without disconnecting, recursive calls keep processing the same list, causing infinite recursion or stack overflow.

3. Final Answer:

   The middle node is not disconnected from the left half, causing infinite recursion. -> Option B

4. Quick Check:

   Disconnect middle to avoid infinite recursion [OK]

Hint: Always break list into two by setting middle's previous next to null [OK]

Common Mistakes:

• Not disconnecting the list at middle
• Wrong base case conditions
• Calling merge before sorting halves
• Assuming GetMiddle returns last node

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

hard

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

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

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

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

Solution

1. Step 1: Understand merge sort handles duplicates by sorting all nodes

   Merge sort compares node values and merges in ascending order, preserving duplicates in sorted order.

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

   Sorted order is 1, 2, 2, 3, 3, so the final list is 1 -> 2 -> 2 -> 3 -> 3 -> null.

3. Final Answer:

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

4. Quick Check:

   Duplicates sorted ascending = 1,2,2,3,3 [OK]

Hint: Merge sort keeps duplicates in sorted order naturally [OK]

Common Mistakes:

• Assuming duplicates get removed
• Mixing order of duplicate nodes
• Not sorting duplicates correctly
• Confusing stable sort with unstable sort