Sort a Linked List Using Merge Sort in DSA Java - Execution Trace

Concept Flow - Sort a Linked List Using Merge Sort

Start with head node

↓

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 Java

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 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 set to null	4 -> 2 -> null 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 set to null	4 -> null 2 -> null
7	Sort left sublist (single node)	1 node: 4 -> null	return 4	4 -> null
8	Sort right sublist (single node)	1 node: 2 -> null	return 2	2 -> null
9	Merge sorted left and right sublists	Nodes: 4, 2	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: 1 -> 3 -> null	mid points to 1	1 -> 3 -> null
12	Split right half	Left: 1 -> null, Right: 3 -> null	mid.next set to null	1 -> null 3 -> null
13	Sort left sublist (single node)	1 node: 1 -> null	return 1	1 -> null
14	Sort right sublist (single node)	1 node: 3 -> null	return 3	3 -> null
15	Merge sorted left and right sublists	Nodes: 1, 3	merge 1 and 3	1 -> 3 -> null
16	Merge two sorted halves	Nodes: 2 -> 4, 1 -> 3	merge 2->4 and 1->3	1 -> 2 -> 3 -> 4 -> null
17	Return fully sorted list	4 nodes: 1 -> 2 -> 3 -> 4 -> null	head points to 1	1 -> 2 -> 3 -> 4 -> null

💡 All nodes merged into a single sorted list; recursion ends.

Variable Tracker

Variable	Start	After Step 3	After Step 9	After Step 15	Final
head	4 -> 2 -> 1 -> 3 -> null	4 -> 2 -> null	2 -> 4 -> null	1 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null
mid	points to 2	points to 4	N/A	points to 1	N/A
left	N/A	4 -> 2 -> null	2 -> 4 -> null	1 -> null	1 -> 2 -> 3 -> 4 -> null
right	N/A	1 -> 3 -> null	N/A	3 -> null	N/A

Key Moments - 3 Insights

Why do we set mid.next to null when splitting the list?

Setting mid.next to null breaks the list into two separate halves, as shown in step 3 and step 6, allowing recursive sorting on independent sublists.

How does the merge function combine two sorted lists?

The merge compares nodes from each list and links the smaller node first, building a sorted list step by step, as seen in steps 9, 15, and 16.

Why do we return the head immediately if the list has zero or one node?

Because a list with zero or one node is already sorted, so recursion stops early, as shown in step 7 and step 13.

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 for step 9 in the execution_table.

At which step does the list first get split into two halves?

A Step 2

B Step 6

C Step 3

D Step 11

💡 Hint

Look for the step where 'mid.next set to null' first appears in the Pointer Changes column.

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

A Step 7

B Step 1

C Step 4

D Step 17

💡 Hint

Refer to the key_moments and execution_table steps where single-node lists return immediately.

Concept Snapshot

Merge Sort on Linked List:
- Base case: empty or single node list returns as is
- Find middle node to split list
- Recursively sort left and right halves
- Merge two sorted halves into one sorted list
- Time complexity: O(n log n), space O(log n) due to recursion

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. We then recursively sort each half until we reach lists with one or zero nodes, which are already sorted. After that, we merge the sorted halves back together step by step, comparing nodes and linking them in order. The process continues until the entire list is sorted. Key steps include breaking the list by setting mid.next to null, sorting sublists, and merging sorted lists. The final output is a fully sorted linked list.

Practice

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

easy

A. Merge sort is easier to implement with arrays than linked lists.

B. Quicksort is faster on linked lists because it uses less memory.

C. Merge sort does not require random access and works well with linked lists.

D. Quicksort always sorts linked lists in O(n) time.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, so algorithms needing it perform poorly.

2. Step 2: Compare merge sort and quicksort

   Merge sort splits and merges lists using pointers, avoiding random access, making it efficient for linked lists.

3. Final Answer:

   Merge sort does not require random access and works well with linked lists. -> Option C

4. Quick Check:

   Merge sort suits linked lists better than quicksort [OK]

Hint: Merge sort fits linked lists due to pointer-based splitting [OK]

Common Mistakes:

• Thinking quicksort is always faster on linked lists
• Assuming arrays and linked lists behave the same
• Ignoring random access needs

2. Which of the following is the correct base case condition in the merge sort function for a linked list?

easy

A. if (head == null) return head.next;

B. if (head == null || head.next == null) return head;

C. if (head.next == null) return null;

D. if (head == null && head.next == null) return null;

Solution

1. Step 1: Identify base case for recursion

   When the list is empty or has one node, it is already sorted.

2. Step 2: Check condition correctness

   Condition 'head == null || head.next == null' correctly checks for empty or single-node list.

3. Final Answer:

   if (head == null || head.next == null) return head; -> Option B

4. Quick Check:

   Base case returns head if list size ≤ 1 [OK]

Hint: Base case: empty or single node list returns itself [OK]

Common Mistakes:

• Using && instead of || in base case
• Returning null incorrectly for single node
• Not handling empty list properly

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

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

   Split into (4 -> 2) and (1 -> 3).

2. Step 2: Recursively sort halves and merge

   Sort (4 -> 2) to (2 -> 4), sort (1 -> 3) to (1 -> 3), then merge to (1 -> 2 -> 3 -> 4).

3. Final Answer:

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

4. Quick Check:

   Sorted list ascending order [OK]

Hint: Merge sorted halves to get fully sorted list [OK]

Common Mistakes:

• Not splitting list correctly
• Merging without sorting halves
• Mixing node order during merge

4. Identify the error in this merge function snippet for linked lists:

Node merge(Node a, Node b) {
  if (a == null) return b;
  if (b == null) return a;
  if (a.data < b.data) {
    a.next = merge(a.next, b);
    return b;
  } else {
    b.next = merge(a, b.next);
    return a;
  }
}

medium

A. The function does not merge nodes recursively.

B. The base cases do not handle null nodes.

C. The comparison operator should be <= instead of <.

D. The function returns the wrong node after recursion.

Solution

1. Step 1: Analyze return statements

   When a.data < b.data, function should return 'a' but returns 'b' incorrectly.

2. Step 2: Correct return node after recursion

   Return the node chosen as smaller to maintain sorted order; here it should be 'a' or 'b' accordingly.

3. Final Answer:

   The function returns the wrong node after recursion. -> Option D

4. Quick Check:

   Return chosen smaller node to merge correctly [OK]

Hint: Return the smaller node after recursive merge [OK]

Common Mistakes:

• Returning wrong node after recursive call
• Ignoring base cases
• Incorrect comparison operator

5. You have a linked list with nodes: 5 -> 3 -> 8 -> 2 -> 7 -> null. After applying merge sort, what is the correct sorted linked list? Also, explain why merge sort is preferred over bubble sort for this linked list.

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists.

B. 8 -> 7 -> 5 -> 3 -> 2 -> null; Bubble sort is faster for small lists.

C. 2 -> 3 -> 5 -> 7 -> 8 -> null; Bubble sort is preferred because it is simpler.

D. 5 -> 3 -> 8 -> 2 -> 7 -> null; Merge sort does not work on linked lists.

Solution

1. Step 1: Sort the list using merge sort

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8 -> null after splitting and merging.

2. Step 2: Explain merge sort advantage

   Merge sort is O(n log n) and uses pointers efficiently; bubble sort is O(n²) and inefficient for linked lists.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists. -> Option A

4. Quick Check:

   Sorted list + merge sort efficiency [OK]

Hint: Merge sort is efficient and stable for linked lists [OK]

Common Mistakes:

• Confusing bubble sort as faster
• Incorrect sorted order
• Thinking merge sort can't handle linked lists