Sort a Linked List Using Merge Sort in DSA Python - 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 list

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

Execution Sample

DSA Python

def merge_sort(head):
    if not head or not head.next:
        return head
    mid = get_middle(head)
    right = mid.next
    mid.next = None
    left_sorted = merge_sort(head)
    right_sorted = merge_sort(right)
    return merge(left_sorted, right_sorted)

This code splits the linked list, sorts each half recursively, 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 = None	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 = None	4 -> null and 2 -> null
7	Sort left part of left half (single node)	1 node: 4 -> null	Return head	4 -> null
8	Sort right part of left half (single node)	1 node: 2 -> null	Return head	2 -> null
9	Merge sorted left parts	Left: 4 -> null, Right: 2 -> null	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 = None	1 -> null and 3 -> null
13	Sort left part of right half (single node)	1 node: 1 -> null	Return head	1 -> null
14	Sort right part of right half (single node)	1 node: 3 -> null	Return head	3 -> null
15	Merge sorted right parts	Left: 1 -> null, Right: 3 -> null	Merge 1 and 3	1 -> 3 -> null
16	Merge two sorted halves	Left: 2 -> 4 -> null, Right: 1 -> 3 -> null	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
18	End	Sorted list returned	No pointer changes	1 -> 2 -> 3 -> 4 -> null

💡 Recursion ends when sublist has 0 or 1 node, then merges build sorted list back up.

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	None	2 -> null	4 -> null	1 -> null	null
left_sorted	None	None	2 -> 4 -> null	2 -> 4 -> null	2 -> 4 -> null
right_sorted	None	None	None	1 -> 3 -> null	1 -> 3 -> null

Key Moments - 3 Insights

Why do we split the list at mid.next and set mid.next = None?

Splitting at mid.next breaks the list into two separate halves so recursion can sort each half independently. See Step 3 where mid.next is set to None to separate left and right halves.

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

A list with zero or one node is already sorted, so recursion returns immediately. This is shown in Steps 7, 8, 13, and 14 where single-node lists return head.

How does merging two sorted lists maintain order?

Merge compares nodes from each half and links the smaller node first, building a sorted list. Step 9 and Step 15 show merging two single-node lists into sorted two-node lists.

Visual Quiz - 3 Questions

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

A 4 -> 2 -> null

B 1 -> 3 -> null

C 2 -> 4 -> 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 recursion first split the list into two halves?

A Step 3

B Step 6

C Step 2

D Step 11

💡 Hint

Look for the step where 'Split list at mid' happens in the execution_table.

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

A Merge would be called immediately

B Function would return head immediately

C Recursion would continue splitting

D List would be split into two empty lists

💡 Hint

Refer to the base case condition in the code and Steps 7, 8, 13, 14 in execution_table.

Concept Snapshot

Merge Sort on Linked List:
- Base case: empty or single node list returns as is
- Find middle node using slow/fast pointers
- Split list into two halves at middle
- Recursively sort each half
- Merge two sorted halves into one sorted list
- Returns 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 process starts by finding the middle node to split the list. The split is done by setting the middle node's next pointer to None, separating the list into two halves. Each half is sorted recursively by the same method. Finally, the two sorted halves are merged by comparing nodes one by one and linking the smaller node first. This continues until the entire list is sorted. The recursion stops when the sublist has one or zero nodes. The final result 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. Quicksort is unstable, but merge sort is always unstable.

B. Merge sort uses less memory than quicksort for linked lists.

C. Merge sort does not require random access, which suits linked lists well.

D. Merge sort sorts linked lists in-place without extra space.

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 by splitting and merging, which only needs sequential access, making it suitable for linked lists.

3. Final Answer:

   Merge sort does not require random access, which suits linked lists well. -> Option C

4. Quick Check:

   Linked list + merge sort = no random access needed [OK]

Hint: Merge sort fits linked lists because it uses sequential access [OK]

Common Mistakes:

• Thinking quicksort is better for linked lists
• Believing merge sort sorts in-place without extra space
• Confusing stability properties of sorting algorithms

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

easy

A. if head is None and head.next is None: return None

B. if head is None or head.next is None: return None

C. if head.next is None: return None

D. if head is None or head.next is None: return head

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: Correct base case condition

   Check if head is None (empty list) or head.next is None (single node), then return head.

3. Final Answer:

   if head is None or head.next is None: return head -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Returning None instead of head for single node
• Using 'and' instead of 'or' in condition
• Missing base case leading to infinite recursion

3. What will be the output linked list after applying merge sort on the following linked list?

4 -> 2 -> 1 -> 3 -> None

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

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

2. Step 2: Recursively sort 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 -> None -> Option A

4. Quick Check:

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

Hint: Merge sort outputs sorted list in ascending order [OK]

Common Mistakes:

• Confusing merge order and producing unsorted output
• Not splitting list correctly
• Merging without sorting halves first

4. Given this merge function snippet for linked lists, what is the bug?

def merge(left, right):
    if not left:
        return right
    if not right:
        return left
    if left.val < right.val:
        result = left
        result.next = merge(left.next, right)
    else:
        result = right
        result.next = merge(left, right.next)
    return result

medium

A. The comparison should be <= instead of < to maintain stability.

B. No bug; function correctly merges two sorted lists.

C. The function does not handle empty lists properly.

D. The function should return None at the end instead of result.

Solution

1. Step 1: Analyze base cases

   Returns right if left is None, and left if right is None, correctly handling empty lists.

2. Step 2: Check recursive merge logic

   Compares values, assigns result, and recursively merges remaining nodes correctly.

3. Final Answer:

   No bug; function correctly merges two sorted lists. -> Option B

4. Quick Check:

   Merge function logic is correct and complete [OK]

Hint: Check base cases and recursion carefully for merge correctness [OK]

Common Mistakes:

• Thinking <= is required for stability (not always needed)
• Missing base case returns
• Returning None instead of merged list

5. You have a linked list with nodes:

5 -> 3 -> 8 -> 2 -> 7 -> None

After applying merge sort, what will be the final linked list? Also, what is the time complexity of merge sort on this linked list?

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n log n)

B. 2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n^2)

C. 5 -> 3 -> 8 -> 2 -> 7 -> None; Time complexity: O(n log n)

D. 3 -> 2 -> 5 -> 7 -> 8 -> None; Time complexity: O(n)

Solution

1. Step 1: Sort the linked list nodes

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8.

2. Step 2: Understand merge sort time complexity

   Merge sort divides list and merges in O(n log n) time for n nodes.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n log n) -> Option A

4. Quick Check:

   Sorted list + merge sort time = O(n log n) [OK]

Hint: Merge sort always sorts in O(n log n) time [OK]

Common Mistakes:

• Confusing time complexity with O(n^2)
• Not sorting nodes correctly
• Assuming merge sort is O(n)